实例参考挑战程序设计BFS的迷宫最短路径


#include <bits/stdc++.h>
#define MAXN 100
using namespace std;

const int INF = 100000000;
typedef pair<int, int> P;	// 定义一个pair类型的数据结构
char maze[MAXN][MAXN+1];	//定义一个保存输入数据的数组
char n, m;					//用来表达矩阵的行列数
int sx, sy; // 起点坐标
int gx, gy; // 终点坐标
int d[MAXN][MAXN];			/*保存的是到达各个位置的最短距离*/
//四个方向的移动量
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int bfs()
{
    queue<P> que;		//首先定义一个队列
    //所有位置初始化为INF
    for( int i=0; i<n; i++ )
        for( int j=0; j<m; j++ )
            d[i][j] = INF;
    //将起点加入队列,并把这一点距离设置为0
    que.push( P(sx, sy) );
    d[sx][sy] = 0;

    while( que.size() ) //队列不为空,表明还没有到达终点
    {
        P p = que.front();  //从队列的最前端取出元素
        que.pop();			//从队列里删除这个已经访问过的元素
        if( p.first == gx && p.second == gy )	//如果访问的这一点是终点,则终止
            break;
        //四个方向的遍历
        for( int i=0; i<4; i++ )
        {
            //移动后的位置记为nx, ny;
            int nx = p.first + dx[i], ny = p.second + dy[i];
            // 在矩阵内且路能走还没有访问过则加入队列
            if( nx >= 0 && nx < n && ny >=0 && ny <m && maze[nx][ny] != '#' && d[nx][ny] == INF )
			{
				que.push( P(nx, ny) );
				d[nx][ny] = d[p.first][p.second] + 1;	// 到这个位置的距离是它的前一点距离加一
			}
        }

    }
	return d[gx][gy];	//返回到终点位置的距离
}
int main()
{
	scanf("%d%d", &n, &m );
	scanf("%d%d", &sx, &sy );
	scanf("%d%d", &gx, &gy );
	getchar();	//吞掉换行符
	for( int i=0; i<n; i++ )
	{
		for( int j=0; j<m; j++ )
			scanf("%c", &maze[i][j] );
		getchar();	//同上
	}
	printf("%d\n", bfs() );



	return 0;
}