欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

OpenJ_Bailian - 3752 走迷宫 (水题:深搜&&广搜 比较)

程序员文章站 2022-05-20 20:49:21
...
一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。
给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。

Input 第一行是两个整数,R和C,代表迷宫的长和宽。( 1<= R,C <= 40)
接下来是R行,每行C个字符,代表整个迷宫。
空地格子用'.'表示,有障碍物的格子用'#'表示。
迷宫左上角和右下角都是'.'。 Output 输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。计算步数要包括起点和终点。 Sample Input
5 5
..###
#....
#.#.#
#.#.#
#.#..
Sample Output
9
一道很经典的模板题,注意终点位置的坐标表示即可,套用bfs和dfs代码如下:DFS(深搜):

#include<bits/stdc++.h>
using namespace std;
char a[101][101];
int vis[101][101];
int amove[4][2]={1,0,-1,0,0,1,0,-1};
int k,n,t,sx,sy,gx,gy,mi=999999;
void dfs(int i,int j,int g)
{
    if(i>=n||j>=n||i<0||j<0||vis[i][j]||a[i][j]=='#') //边界处理 
        return;
    if(i == gx && j == gy)
    {
        if(g<mi)
        mi=g;
        return;
    }
    vis[i][j]=1;
    for(int p=0;p<4;p++)
        dfs(i+ amove[ p][ 0],j+ amove[ p][ 1],g+1);
}
int main()
{
    scanf("%d%d", &k, &n);
    for(int i=0;i<n;i++)
    scanf("%s",a[i]);
    gx=k-1;
    gy=n-1;
    dfs(0,0,1);
    printf("%d\n",mi); 
}

BFS(广搜):

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;i++)
char map[50][50];
int vis[50][50];
int len,wid;
int gx,gy;
int amove[4][2]={0,1,0,-1,-1,0,1,0};
typedef struct Node{
int posx;
int posy;
int step;
Node(){}
Node(int x,int y,int s):posx(x),posy(y),step(s){}	
};
queue<Node> q;
int bfs(){
	int nx,ny;
	Node now;
	Node next;
	while(!q.empty())
	q.pop();
	q.push(Node(1, 1, 1));
	
	while(!q.empty()){
		now=q.front();
		q.pop();
		if(now.posx == gx && now.posy == gy ) return now.step;
		FOR(d,0,3){
			nx = now.posx+ amove[ d][ 0]; //更新x坐标 
			ny = now.posy+ amove[ d][ 1]; //更新y坐标 
			next=Node (nx, ny, now.step+1);
			if(nx<= 0 || nx> len || ny<= 0 || ny> wid) continue ; //边界处理 
			if(vis[ nx][ ny]== 0 && map[ nx][ ny]=='.') {
			
				vis[ nx][ ny]= 1;
				q.push(next);	
			}
		}
		
	}
	return -1;
}

int main(){
cin>> len>> wid;  	 
FOR(i, 1, len) FOR(j, 1, wid) cin>> map[ i][ j];
    gx= len;
	gy= wid;   
	cout << bfs();	
} 

      运行之后,发现广搜算法用时更短。比较思考之后,发觉原因在于 深搜是对一条路走到底 碰到死胡同(即另三个方向都是#或边界)才会跳出,进行另一条路的搜索。而广搜则通过队列的进栈出栈,遍历了每一固定步数所可能到达的不重复所有位置,一旦到达终点,则返回步数。因此,在该类求最小值或唯一路径的问题上,广搜往往用时更少。