实例参考挑战程序设计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;
}