迷宫问题
Time Limit: 1000MS Memory Limit: 65536K
Description
定义一个二维数组:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径,格式如样例所示。
Sample Input
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4
解题思路
这个题其实有点搞笑,POJ上居然只有一组数据,水题中的水题......我后来用的是Acwing上的测评系统,还是很正常的hhh。
这道题是经典的BFS求最短路模型,但是需要我们去输出具体的路径,这是比较考验逆向思维的地方。要求出从左上角到右下角的最短路的具体方案,以正向思维来考虑是不太行的,从走出的第一步开始,你便不知道到底走到哪个方向会求得未来的最优解。所以,我们需要采取一种逆向思维,即以所要到达的终点为起点进行BFS。在BFS过程中,每个点第一次访问一定是距离最短的,所以由此可以求出所有点的前驱,直到到达左上角。然后从左上角这个点开始反向输出所有记录的前驱,就可以得到最优且合法的到达右下角的具体路径。
/* 一切都是命运石之门的选择 El Psy Kongroo */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, pii> psi;
typedef __int128 int128;
#define PI acos(-1.0)
#define x first
#define y second
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 1010;
bool vis[N][N];
int g[N][N];
pii pre[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n;
void bfs(){
queue<pii> q;
q.push(make_pair(n - 1, n - 1));
vis[n - 1][n - 1] = true;
while(!q.empty()){
pii p = q.front();
int x = p.first, y = p.second;
q.pop();
for(int k = 0; k < 4; k ++ ){
int nx = x + dx[k], ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if(g[nx][ny] || vis[nx][ny]) continue;
q.push(make_pair(nx, ny));
vis[nx][ny] = true;
pre[nx][ny] = p;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0; i < n; i ++ )
for(int j = 0; j < n; j ++ )
cin >> g[i][j];
bfs();
//输出反向bfs的前驱,即正向的路径
pii end = make_pair(0, 0);
while(end.first != n - 1 || end.second != n - 1){
int x = end.first, y = end.second;
cout << x << ' ' << y << endl;
end = pre[x][y];
}
cout << n - 1 << ' ' << n - 1;
return 0;
}
标签:pair,typedef,int,nx,ny,POJ,kuangbin,3984,include
From: https://www.cnblogs.com/MAKISE004/p/17321795.html