Problem 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
- 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)
也是 kuangbin 搜索专题里面的, 说起这道题, 也是满满的恶意, 先看图吧
整整花了一个小时去找到底哪里 PE 了.
题目思路很明确, BFS 或者 DFS 都可以, 但其实这个题目没必要 DFS, 简单 BFS 标记一下前驱就行了, 何为前驱, 就是说你走到了下一步你上一步 是从哪里走来的, 然后用优先队列保证每次优先走距离右下角最近的路. 那么问题来了, 如何输出, 因为我们存的是前驱, 所以可以先把所有前驱 入栈, 再依次出栈输出就行了, 但最开始我想到了另一种更好的方法, 因为我发现
- ostringstream outt;
- outt <<2 << 1 << 3;
- string s = outt.str();
- reverse(s.begin(), s.end());
- cout << s << endl;
利用 ostringstream 流, 最后倒过来就可以实现直接顺序输出了, 提交 PE. 找了半天发现是 <<endl; 倒序后变成先输出了, 那么我第一个不加 endl, 再次提交 PE,PE,PE,PE. 到这里我觉得可能是 ostringstream 影响缓冲区, 不能这样, 改成栈模拟, 还是 PE =7=, 直到最后我发现,(a, b) 中间 逗号后面 有个空格 / 微笑 / 微笑. 然后改了两种方法都 AC 了;
AC 代码
- #include <iostream>
- #include <string>
- #include <cstdio>
- #include <cstdlib>
- #include <sstream>
- #include <iomanip>
- #include <map>
- #include <stack>
- #include <deque>
- #include <queue>
- #include <vector>
- #include <set>
- #include <list>
- #include <cstring>
- #include <cctype>
- #include <algorithm>
- #include <iterator>
- #include <cmath>
- #include <bitset>
- #include <ctime>
- #include <fstream>
- #include <limits.h>
- #include <numeric>
- using namespace std;
- #define F first
- #define S second
- #define mian main
- #define ture true
- #define MAXN 1000000+5
- #define MOD 1000000007
- #define PI (acos(-1.0))
- #define EPS 1e-6
- #define MMT(s) memset(s, 0, sizeof s)
- typedef unsigned long long ull;
- typedef long long ll;
- typedef double db;
- typedef long double ldb;
- typedef stringstream sstm;
- const int INF = 0x3f3f3f3f;
- int mp[5][5],vis[5][5];
- int fx[4][2] = {1,0,-1,0,0,-1,0,1};
- vector<pair< int, pair<int,int>>>bj(40); // 记录前驱和位置
- ostringstream outt;
- class cmp{ // 优先队列使得曼哈顿距离小的优先出队
- public:
- bool operator() (const pair<int,int>a,const pair<int,int>b) const{
- int ax = 4 - a.F + 4 - a.S;
- int bx = 4 - b.F + 4 - b.S;
- return ax> bx;
- }
- };
- void bfs(){
- priority_queue<pair<int,int>,vector<pair<int,int>>, cmp>q;
- //queue<pair<int,int>>q;
- q.push(make_pair(0,0));
- vis[0][0] = 1;
- while(!q.empty()){
- pair<int,int>nx = q.top();
- q.pop();
- //cout <<nx.F << " " << nx.S << endl;
- if(8 - (nx.F + nx.S) == 1){
- bj[24].F = nx.F*5+nx.S;
- bj[24].S.F = 4, bj[24].S.S = 4;
- break;
- }
- for(int i = 0; i < 4; i++){
- int nxx = nx.F + fx[i][0];
- int nxy = nx.S + fx[i][1];
- if(nxx < 0 || nxx> 4 || nxy <0 || nxy> 4 || mp[nxx][nxy] == 1 || vis[nxx][nxy])
- continue;
- vis[nxx][nxy] = 1;
- q.push(make_pair(nxx,nxy));
- bj[nxx*5+nxy].F = nx.F*5+nx.S;
- bj[nxx*5+nxy].S.F = nxx, bj[nxx*5+nxy].S.S = nxy;
- }
- }
- int nex = 24;
- /*// 这是用栈模拟的方式
- stack<int>p;
- while(nex){
- p.push(nex);
- nex = bj[nex].F;
- }
- p.push(0);
- while(!p.empty()){
- nex = p.top();
- p.pop();
- cout <<"(" << bj[nex].S.F << "," << bj[nex].S.S << ")"<< endl;
- }
- */
- while(1){ // 反向输出到 ostringstream 中
- //cout << nex << endl;
- if(nex == 0){
- outt << ")" << bj[nex].S.S << "," << bj[nex].S.F << "(";
- break;
- }
- outt << ")" << bj[nex].S.S << "," << bj[nex].S.F << "(" << "\n";
- nex = bj[nex].F;
- }
- }
- int main(){
- ios_base::sync_with_stdio(false);
- cout.tie(0);
- cin.tie(0);
- fill(vis[0],vis[0]+5*5,0);
- for(int i = 0; i < 5; i++){
- for(int j = 0; j < 5; j++){
- cin>>mp[i][j];
- }
- }
- bfs();
- string s = outt.str();
- reverse(s.begin(),s.end()); // 再次逆序
- cout << s << endl;
- return 0;
- }
其他就是一个简单的 BFS, 值得注意就是优先队列的使用, 当然用 DFS 也行 , 而且 DFS 就不需要这么多繁杂的逆序了, 直接记录从起点到终点的路径输出就好了.
来源: http://www.bubuko.com/infodetail-2727491.html