昨天中午做的这道题，结果蛙了一整天，就因为一行代码困住了，今天算是见识到自己有多菜了。流泪.jpg
本题大意：给一个5 * 5的迷宫，1表示墙壁，0表示通路，从左上角走到右下角并输出路径。
本题思路：主要就是BFS寻路，为了方便打印，从右下角开始进行BFS。
注意输出时候的大坑，会有标记。
本题代码：
#include <cstdio>
#include <queue>
#include <map>
using namespace std; typedef pair<int ,int > P;
const int n = , INF = 1e7;
int maze[n][n], d[n][n], dx[] = {, , -, }, dy[] = {, , , -};
P path[n][n];//用来保存每个结点的父节点，方便输出 void bfs() {
queue <P> s;
s.push(P(, ));//从终点到起点方便路径打印
for(int i = ; i < n; i ++)
for(int j = ; j < n; j ++) {
d[i][j] = INF;
path[i][j] = P(-, -);
}
d[][] = ;
while(s.size()) {
P p = s.front();
if(p.first == && p.second == ) break;
s.pop();
for(int i = ; i < ; i ++) {
int nx = p.first + dx[i], ny = p.second + dy[i];
if(nx >= && nx < n && ny >= && ny < n && maze[nx][ny] == && d[nx][ny] == INF) {
s.push(P(nx, ny));
d[nx][ny] = d[p.first][p.second] + ;
path[nx][ny] = P(p.first, p.second);
}
}
}
} int main () {
for(int i = ; i < n; i ++)
for(int j = ; j < n; j ++)
scanf("%d", &maze[i][j]);
bfs();
P p = make_pair(, );
while(p.first != -) {
printf("(%d, %d)\n", p.first, p.second);
int tmp = p.first;//这个很坑，坑了我4个小时，修改值之前进行记录
p.first = path[p.first][p.second].first;
p.second = path[tmp][p.second].second;
}
return ;
}