迷宫问题【POJ3984】

题目链接

输出路径的BFS

POJ似乎不能使用C++11中的初始化方式 pair类型的插入需要用make_pair(a, b)

#include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <queue> using namespace std; typedef pair<int, int> PII; const int N = 1e3+5; int g[N][N]; int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1}; PII pre[N][N];//pair类型的二维数组，相当于每个位置放置的是一个pair类型 void bfs(int u, int v){ queue<PII> q; q.push(make_pair(u, v)); while(q.size()){ PII t = q.front(); q.pop(); for(int i = 0; i < 4; i++){ int a = t.first + dx[i]; int b = t.second + dy[i]; if(a < 0 || b < 0||a >= 5 || b >=5 || g[a][b] == 1) continue; g[a][b] = 1; pre[a][b] = t; q.push(make_pair(a, b)); } } } int main(){ for(int i =0; i < 5; i ++) for(int j = 0; j < 5; j++) scanf("%d", &g[i][j]); bfs(4,4); //倒着搜 PII end(0,0); while(true){ printf("(%d, %d)\n", end.first, end.second); if(end.first == 4 && end.second == 4) break; end = pre[end.first][end.second]; } return 0; }