迷宫问题 （C++代码）

解题思路:使用宽度优先搜索，在计算最短路径时采用坐标方式计算d[nextx][nexty]=d[nowx][nowy]+1来更新路径值

注意事项:坐标存储有两种方式pair<int,int>p或者结构体

参考代码:

#include<iostream>
#include<queue>
using namespace std;
const int INF=1000000;
char arr[100][100];
int d[100][100];//路径坐标
int n,m,k;
int sx,sy,ex,ey;//起终点坐标
int index[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //四个方向

struct Indexnum
{
	int x1;
	int y1;
};
int  bfs(Indexnum x)
{
	for(int i=0;i<m;i++)//初始化
	{
		for(int j=0;j<k;j++)
		{
			d[i][j]=INF;
		}
	}
	queue<Indexnum>q1;
	int cnt=0;
	q1.push(x);
	d[sx][sy]=0;
	while(!q1.empty())
	{
		Indexnum p,p1;
		p=q1.front();
		q1.pop();
		if(p.x1==ex && p.y1==ey)
		{
			break;
		}
		for(int i=0;i<4;i++)
		{
			int x2=p.x1+index[i][0];//更新坐标
			int y2=p.y1+index[i][1];
			if(x2>=0 && x2<m && y2>=0 && y2<k && d[x2][y2]==INF&& arr[x2][y2]!='#')
			{
				p1.x1=x2;
				p1.y1=y2;
				d[x2][y2]=d[p.x1][p.y1]+1;//更新路径长度
				q1.push(p1);
			}
		}
	}
	return d[ex][ey];
}
int main()
{
	
	cin>>n;
	while(n!=0)
	{
		cin>>m>>k;
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<k;j++)
			{
				cin>>arr[i][j];
				if(arr[i][j]=='S')
				{
					sx=i;
					sy=j;
				}
				if(arr[i][j]=='E')
				{
					ex=i;
					ey=j;
				}
			}
		}
		Indexnum g;
		g.x1=sx;
		g.y1=sy;
		if(bfs(g)==INF)//路径不可达
		{
			cout<<"-1"<<endl;
		} 
		else
		{
			cout<<bfs(g)<<endl;
		}
		n--;
	}
	return 0;
}