bfs搜索过程中将路径保存下即可。
AC代码
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn = 10; int G[maxn][maxn], d[maxn][maxn], pre[40]; const int dx[] = {1,-1,0,0}; const int dy[] = {0,0,-1,1}; void print(int x, int y){ int pos = pre[x * 5 + y]; if(pos != -1) print(pos / 5, pos % 5); printf("(%d, %d)\n", x, y); } void bfs(){ memset(d, -1, sizeof(d)); pre[0] = -1; queue<int>q; q.push(0); d[0][0] = 0; while(!q.empty()) { int pos = q.front(); q.pop(); int x = pos / 5, y = pos % 5; if(x == 4 && y == 4) { print(x, y); return; } for(int i = 0; i < 4; ++i){ int px = x + dx[i], py = y + dy[i]; if(px < 0 || py < 0 || px >= 5 || py >= 5) continue; if(G[px][py] || d[px][py] != -1) continue; d[px][py] = d[x][y] + 1; pre[px * 5 + py] = x * 5 + y; q.push(px * 5 + py); } } } int main(){ for(int i = 0; i < 5; ++i) for(int j = 0; j < 5; ++j){ scanf("%d", &G[i][j]); } bfs(); return 0; }
如有不当之处欢迎指出!