2178迷宫问题 中等BFS+DFS(注释很详细)

注意:这里的前半段BFS代码直接套用第2177题的代码,稍作修改即可

原版在我的这篇题解:<2177走迷宫 简单BFS(注释很详细)>

其实BFS像是从一个点,一片一片地拓展出去,而DFS更像是从一个点,以线的形式延伸出去.

这道题在第2177题的基础上要求输出具体的最短路径是什么.

而那一条最短路径也是一条线,与DFS的结果形式相似,故而想到用DFS

/*BFS思想:从同一起点出发,每次都向前走一步,更短的路径一定会更快地到达终点,
终点的层数(到达要花的步数)也会相应地更新为最小层数*/

#include<bits/stdc++.h>

using namespace std;

#define INF 9999999;

int R,C;

int i,j;

typedef struct Point
{
	int x;
	int y;
	int cell;//单元格cell(1或者0)
	int layer;//方便BFS的层数(layer)统计,同时也可以表示到达一点要花的步数
}Point;

Point M[6][6];//Point Map

int book[6][6];//用于判断该点是否走过

int nx,ny;//next_x,next_y

int sx = 1, sy = 1;//start_x,start_y起点坐标

int ex,ey;//end_x,end_y终点坐标

Point point;

queue <Point> que;

int Next[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
//方向数组,next[i][0]表示行坐标,next[i][1]表示列坐标
//左上右下的顺序

int target;//目标target,用于记录最小步数

int flag;//用于判断dfs的退出条件

void dfs(int x,int y,int n);

int main()
{
	R=5;
	C=5;
	//如果是大小不同的矩阵,改R,C值即可

	for(i = 1; i <= R;i++)
	{
		for(j = 1; j <= C; j++)
		{
			scanf("%d",&M[i][j].cell);
			M[i][j].x = i;
			M[i][j].y = j;
			M[i][j].layer = INF;
			//初始化为INF,即到达不了
		}
		getchar();//一定要加,不然就会地图读取错误
	}

	que.push(M[sx][sy]);
	book[sx][sy] = 1;
	M[sx][sy].layer = 1;
	//从地图左上角出发
	//如果有从其他地方出发的需求可以改值

	ex = R;
	ey = C;
	//设置终点

	while(que.empty() != 1)
	{
		point = que.front();
		que.pop();
		//接收到队首元素后就弹出队首元素(不需要它了)

		for(i = 0; i <= 3; i++)
		{
			nx = point.x + Next[i][0];
			ny = point.y + Next[i][1];

			if(nx>= 1 && nx <= R && ny >=1 && ny <= C//不出界
			&& M[nx][ny].cell == 0 && book[nx][ny] == 0)//是空地格子并且没有走过
			{
				book[nx][ny] = 1;//标记为走过

				M[nx][ny].layer = M[point.x][point.y].layer + 1;//意为:多一步就可以到

				que.push(M[nx][ny]);//入队

				if(nx == ex && ny == ey)
				{
					break;
					//剪枝
					//如果终点已经入队了,证明终点的步数就已经确定了,不用再进行了
				}
			}
		}
		if(nx == ex && ny == ey)
		{
			break;
			//继续跳出循环
		}
	}
	
	target = M[ex][ny].layer;
	
	memset(book,0,sizeof(int)*36);
	//book清空,方便dfs查询
	
	dfs(ex,ey,1);
	/*由于栈FILO(First In Last Out先进后出)的特性,
	为了方便输出顺序,由终点进入循环,找到起点后层层退出*/
	
	return 0;
}

/*DFS思想:从终点开始,延伸很多条线出去,最短的并且可以到达起点的那条就是最短路径*/

void dfs(int x,int y,int n)
//n是指目前的步数
{
	int i;
	if((n == target && x == sx && y == sy) || flag == 1)
	//由于已经通过BFS算出了最短步数,所以可以直接判断从终点到起点花的步数是非为该值
	{
		flag = 1;
		printf("(%d, %d)\n",x-1,y-1);
		return;
	}
	
	if(n > target)
	//大于最短步数的可以剪枝
	{
		return;
	}
	
	for(i = 0; i <= 3; i++)
	{
		nx = x + Next[i][0];
		ny = y + Next[i][1];

		if(nx>= 1 && nx <= R && ny >=1 && ny <= C//不出界
		&& M[nx][ny].cell == 0 && book[nx][ny] == 0)//是空地格子并且没有走过
		{
			book[nx][ny] = 1;//标记为走过
			
			dfs(nx,ny,n+1);
			//进入该点
			
			if(flag == 1)
			//如果已经确认了这条路是最短路径了,就不用再循环了,直接一路全部printf然后return就好了
			{
				printf("(%d, %d)\n",x-1,y-1);
				return;
			}
			
			book[nx][ny] = 0;
			//如果回退了,就要清除book,表示没有走过
		}
	}
	
	return;
}

    另外,这道题也可以用单纯的BFS或者DFS解,这里就不赘述了.