POJ 3984---迷宫问题(BFS，迷宫最短路径且输出路径) BFS

原题：
【POJ 3984---迷宫问题(BFS，迷宫最短路径且输出路径)】BFS入门题，打印路径记录前驱就可以了。然后可以递归打印，也可以非递归打印路径：
递归打印路径：

#include #include #include #include #includeusing namespace std; int maze[6][6]; int vis[6][6], dist[6][6]; int dr[] = { -1,1,0,0 }; int dc[] = { 0,0,1,-1 }; struct node { int r, c; }pre[6][6]; queueQ; void bfs() { while (!Q.empty())Q.pop(); memset(vis, 0, sizeof(vis)); dist[0][0] = 0; node tmp; tmp.c = tmp.r = 0; Q.push(tmp); while (Q.size()) { node tmp = Q.front(); Q.pop(); int r = tmp.r, c = tmp.c; for (int i = 0; i < 4; i++) { int nr = r + dr[i], nc = c + dc[i]; if (nr >= 0 && nr <= 4 && nc >= 0 && nc <= 4 && !vis[nr][nc] && maze[nr][nc] == 0) { vis[nr][nc] = 1; tmp.c = nc; tmp.r = nr; Q.push(tmp); dist[nr][nc] = dist[r][c] + 1; tmp.r = r; tmp.c = c; pre[nr][nc] = tmp; //丫丫的，好不方便~可是我不会C++呀。 if (nr == 4 && nc == 4)return; } } } } void print(int x, int y) //递归打印 { if (x == 0 && y == 0)return; print(pre[x][y].r, pre[x][y].c); printf("(%d, %d)\n", pre[x][y].r, pre[x][y].c); } int main() { for(int i=0; i<5; i++) for (int j = 0; j < 5; j++) cin >> maze[i][j]; bfs(); print(4, 4); cout << "(4, 4)" << endl; system("pause"); }

非递归：

#include #include #include #include #includeusing namespace std; int maze[6][6]; int vis[6][6], dist[6][6]; int dr[] = { -1,1,0,0 }; int dc[] = { 0,0,1,-1 }; struct node { int r, c; }pre[6][6]; queueQ; void bfs() { while (!Q.empty())Q.pop(); memset(vis, 0, sizeof(vis)); dist[0][0] = 0; node tmp; tmp.c = tmp.r = 0; Q.push(tmp); while (Q.size()) { node tmp = Q.front(); Q.pop(); int r = tmp.r, c = tmp.c; for (int i = 0; i < 4; i++) { int nr = r + dr[i], nc = c + dc[i]; if (nr >= 0 && nr <= 4 && nc >= 0 && nc <= 4 && !vis[nr][nc] && maze[nr][nc] == 0) { vis[nr][nc] = 1; tmp.c = nc; tmp.r = nr; Q.push(tmp); dist[nr][nc] = dist[r][c] + 1; tmp.r = r; tmp.c = c; pre[nr][nc] = tmp; //丫丫的，好不方便~可是我不会C++呀。 if (nr == 4 && nc == 4)return; } } } } int main() { for(int i=0; i<5; i++) for (int j = 0; j < 5; j++) cin >> maze[i][j]; bfs(); stackS; int cur_r = 4, cur_c = 4; while (1) { node tmp; tmp.r = cur_r; tmp.c = cur_c; S.push(tmp); if (cur_r == 0 && cur_c == 0) break; int r = cur_r, c = cur_c; cur_r = pre[r][c].r; cur_c = pre[r][c].c; } while (S.size()) { node tmp = S.top(); S.pop(); printf("(%d, %d)\n", tmp.r, tmp.c); } system("pause"); }