定义一个二维数组：
代码语言：javascript复制int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
此题题意比较简单，就是找一条左上到右下的最短路，并打印出来。这种简单的最短路直接 BFS 就解决了。稍微麻烦一点在于打印，那么该如何去储存这条最短路线呢？题目明确指出打印出坐标，那直接用个 pair 储存一下 x, y 就好了，可以尝试建立一个 pair 数组，又需要路线，那我们存一下前驱坐标就行了。问题来了，从哪端开始存方便一些，如果从起始坐标 (0, 0) 处就存的话，结点必然不唯一，比如说离 (0, 0) 距离为 1 的可能就好几个（ps：此处不理解的话可以去看看 floodfill）。所以尝试一下从结尾处开始存，结尾处的结点前驱就唯一了，想一想为什么？然而从结尾开始存的话又需要一个栈倒一下顺序，那直接从 (4, 4) 向 (0, 0)搜索就好了。
代码语言：javascript复制#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define sf scanf
#define pf printf
#define rep(i,a,b) for(int i=a;i<(b); i)
bool mm[6][6];
pair<int,int> pre[5][5];
void bfs(int x, int y) {
queue<pair<int, int> > qq; qq.push(mp(x, y));
while(!qq.empty()) {
int inext[] = {0, 0, -1, 1};
int jnext[] = {-1, 1, 0, 0};
rep(k, 0, 4) { // 结点的上下左右各查找一次
int icur = qq.front().fi inext[k];
int jcur = qq.front().se jnext[k];
if(icur < 0 || icur >4 || jcur < 0 || // 去除越界位置
jcur > 4 || (icur == x && jcur == y)) continue;
if(!mm[icur][jcur] && !pre[icur][jcur].first) { // 能走并且未走过(pair元素默认为空)
qq.push(mp(icur, jcur)); // 加入队列
// 此时的队首元素即为下一个结点的前驱，不熟悉的朋友可以建立如下结构，熟悉一下BFS，打印出来观察一下
// fg[icur][jcur] = fg[qq.front().first][qq.front().second] 1;
// fg[i][j]：i, j位置离起点的最短距离
pre[icur][jcur] = qq.front(); // 记录前驱位置
}
if(icur == 0 && jcur == 0) return; // 到终点了就退出
}
qq.pop(); // 查找过的结点就直接pop
}
}
int main() {
//freopen("D:\i.txt","r",stdin);
rep(i, 0, 5) rep(j, 0, 5) cin>>mm[i][j];
bfs(4, 4);
puts("(0, 0)");
pair<int, int> tmp(0, 0);
while(tmp.fi != 4 || tmp.se != 4) {
int i = tmp.fi;
int j = tmp.se;
pf("(%d, %d)n", pre[i][j].fi, pre[i][j].se);
tmp = pre[i][j];
}
return 0;
}
