贪吃蛇 迷宫问题

链接[牛客网]

( https://ac.nowcoder.com/acm/contest/9986/I )

题目描述

无限增长的贪吃蛇小游戏：

在一个n*m的迷宫中，有一条小蛇，地图中有很多围墙，猥琐的出题者用“#”表示，而可以走的路用“.”表示，小蛇他随机出生在一个点上，出生点表示为“S”，他想抵达的终点表示为“E”，小蛇有一个奇怪的能力，他每走一格便会增长一格，即他走了一格后，他的尾巴不会缩回。

小蛇想知道他怎么到达他想去的地方，请你帮助他。

PS：每格长1米，贪吃蛇规定不能撞墙，不能咬自己的身体。

输入描述

第一行：输入N,M；

第二行：输入S的坐标Xs，Ys，E的坐标Xe，Ye;

后面的N行：

每行输入M个数，描述每一行的情况。

输出描述

输出一个数，小蛇到达终点的最短距离（单位：cm），若无法达到，输出-1。

样例

示例一

输入
3 3
1 1 3 3
.#.
.#.
…
输出
400

示例二

输入
5 5
1 1 5 5
…###
.#…
.#.#.
.#.#.
…#.
输出
1400

解题思路

• 根据题意可知，是一个走迷宫的最短路问题，使用dfs或者bfs的模板即可求解。

解题代码

• DFS解题代码

#include<bits/stdc++.h>
using namespace std;
const int N=1002000;
int n,m;//地图大小
int mi=9999999;
int sx, sy, p, q,step=0;
char dt[N][N];//地图数组
bool b[N][N];//初始化为0，表示都未访问

void dfs(int x,int y,int step){
	//四个方向的位移数组
    int next[3][2]={
        {0,1},
        {-1,0},
        {1,0}
    };
    int tx, ty;
    if(x==p && y==q){
        if(step<mi){
            mi=step;
            return;
        }
    }
    for(int k=0;k<=2;k++){
        tx=x+next[k][0];
        ty=y+next[k][1];
        if(tx>n || tx<1 ||ty>m ||ty<1)continue;
        if(dt[tx][ty] == '.' && b[tx][ty]==0){
            b[tx][ty]=1;
            dfs(tx,ty,step+1);//访问下一节点
            b[tx][ty]=0;//访问过后取消标记
        }
    }
    return;
}

int main(){
    scanf("%d %d",&n,&m);
    scanf("%d %d %d %d",&sx,&sy,&p,&q);
    for(int i=1;i<=n;i++){
        getchar();
        for(int j=1;j<=m;j++){
            scanf("%c",&dt[i][j]);
        }
        
    }
    b[sx][sy]=1;
    dfs(sx,sy,0);
    if(mi==9999999){
        printf("-1");
    }
    else{
        printf("%d",mi*100);
    }
    return 0;
}

• BFS解题代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000020;

int n,m,tt=1,hh=1;
char ma[N][N];
int sx,sy,p,q;
bool b[N][N];//初始化为0，表示都未访问

int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//位移数组
//结构体模拟队列
struct note{
	int x;
	int y;
	int step;
}que[N*N];

int main(){
	scanf("%d %d",&n,&m);
	scanf("%d %d %d %d",&sx,&sy,&p,&q);
	for(int i=1;i<=n;i++){
		getchar();
		for(int j=1;j<=m;j++){
			scanf("%c",&ma[i][j]);
		}
	}
	//将初始位置放入队列
	que[tt].x = sx;
	que[tt].y = sy;
	que[tt].step = 0;
	tt++;
	b[sx][sy]=1;
	int f=0;
	while(hh<tt){
		for(int i=0;i<=3;i++){
			int datex=que[hh].x +next[i][0];
			int datey=que[hh].y +next[i][1];
			if(datex<0 || datex>n || datey<0 || datey>m)continue;
			if(ma[datex][datey]=='.' && b[datex][datey]==0){
				//队列中每个元素只入队一次，不需要再还原已访问的位置
				b[datex][datey]=1;//标记已访问
				que[tt].x = datex;
				que[tt].y = datey;
				que[tt].step = que[hh].step+1;
				tt++;
			}
			if(datex==p && datey==q){
				//下面两句话的位置不能反
				f=1;
				break;
			}
		}
		if(f==1){
			break;
		}
		hh++;//必不可少，在一个点扩展结束后，hh++才能对后面的点进行扩展
	}
	if(f==1)printf("%d",que[tt-1].step*100);
	else cout<<-1;
	return 0;
}