bfs计算走迷宫最短路径+dfs回溯路径

bfs计算走迷宫最短路径,并且记录路径

代码

#include 
#include 
#include 
#include 
using namespace std;
string ans;
char map[100][100];
int book[100][100], n, m, cnt;
int nextx[4]={1,0,0,-1};//下、右、左、上  
int nexty[4]={0,1,-1,0};  
struct node
{
	int x, y;
	int s;
};
struct father // 路径记录 
{
	int x, y;
	char way;
};
queue q;
node start, finsh;
father road[100][100];
int bfs()
{
	int i, j;
	// 初始化 
	start.x = 0; // 起点左上角 
	start.y = 0;
	start.s = 0;
	finsh.x = n - 1; // 终点右下角 
	finsh.y = m - 1;
	q.push(start);
	book[start.x][start.y] = 1;
	while(!q.empty())
	{
		node now = q.front();
		q.pop();
		for(i=0; i<4; i++)
		{
			node New;
			// 4个方向判断 
			New.x = now.x + nextx[i];
			New.y = now.y + nexty[i];
			New.s = now.s + 1;
			// 边界判断 
			if(New.x < 0 || New.y < 0 || New.x >= n || New.y >= m || book[New.x][New.y] || map[New.x][New.y]=='0')
				continue;
			q.push(New);
			road[New.x][New.y].x = now.x;
			road[New.x][New.y].y = now.y;
			if(i == 0) // 判断当前可行解方向 
				road[New.x][New.y].way='S';  
            else if(i == 1)   
				road[New.x][New.y].way='D';  
            else if(i == 2)   
				road[New.x][New.y].way='A';  
            else if(i == 3)   
				road[New.x][New.y].way='W';  
			book[New.x][New.y] = 1; // 防止重复走 
			if(New.x == finsh.x && New.y == finsh.y) // 走到终点结束 
				return New.s;
		}
	}
	return -1; // 无解返回-1 
}
void dfs(int x, int y) // 回溯路径并保存 
{
	if(x == 0 && y == 0)
		return;
	else
		dfs(road[x][y].x, road[x][y].y); // 递归回溯路径
	ans += road[x][y].way; 
}
void change() // 统计转向次数 
{
	char same;
	same = ans[0];
	for(int i=0; i> n >> m;
	for(i=0; i> map[i][j];
	res = bfs();
	cout << ans;
	dfs(n-1, m-1); 
	change();	
	cout << "最短路径:" << res << endl;
	cout << "最佳解(W上,S下,A左,D右):" << ans << endl;
	cout << "转向次数:" << cnt << endl; 
}