迷宫问题【POJ3984】

本文主要是介绍迷宫问题【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;
}

这篇关于迷宫问题【POJ3984】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---