+关注继续查看

# 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,
};

# 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搜索专题里面的，说起这道题，也是满满的恶意，先看图吧

ostringstream outt;
outt << 2 << 1 << 3;

string s = outt.str();
reverse(s.begin(), s.end());
cout << s << endl;

AC代码

  1 #include <iostream>
2 #include <string>
3 #include <cstdio>
4 #include <cstdlib>
5 #include <sstream>
6 #include <iomanip>
7 #include <map>
8 #include <stack>
9 #include <deque>
10 #include <queue>
11 #include <vector>
12 #include <set>
13 #include <list>
14 #include <cstring>
15 #include <cctype>
16 #include <algorithm>
17 #include <iterator>
18 #include <cmath>
19 #include <bitset>
20 #include <ctime>
21 #include <fstream>
22 #include <limits.h>
23 #include <numeric>
24
25 using namespace std;
26
27 #define F first
28 #define S second
29 #define mian main
30 #define ture true
31
32 #define MAXN 1000000+5
33 #define MOD 1000000007
34 #define PI (acos(-1.0))
35 #define EPS 1e-6
36 #define MMT(s) memset(s, 0, sizeof s)
37 typedef unsigned long long ull;
38 typedef long long ll;
39 typedef double db;
40 typedef long double ldb;
41 typedef stringstream sstm;
42 const int INF = 0x3f3f3f3f;
43
44 int mp[5][5],vis[5][5];
45 int fx[4][2] = {1,0,-1,0,0,-1,0,1};
46 vector< pair< int, pair<int,int> > >bj(40); //记录前驱和位置
47 ostringstream outt;
48 class cmp{  //优先队列使得曼哈顿距离小的优先出队
49 public:
50     bool operator() (const pair<int,int>a,const pair<int,int>b) const{
51         int ax = 4 - a.F + 4 - a.S;
52         int bx = 4 - b.F + 4 - b.S;
53         return ax > bx;
54     }
55 };
56
57 void bfs(){
58     priority_queue< pair<int,int>,vector< pair<int,int> >, cmp >q;
59     //queue< pair<int,int> >q;
60     q.push(make_pair(0,0));
61     vis[0][0] = 1;
62     while(!q.empty()){
63         pair<int,int>nx = q.top();
64         q.pop();
65         //cout << nx.F << " " << nx.S << endl;
66         if(8 - (nx.F + nx.S) == 1){
67             bj[24].F = nx.F*5+nx.S;
68             bj[24].S.F = 4, bj[24].S.S = 4;
69             break;
70         }
71
72         for(int i = 0; i < 4; i++){
73             int nxx = nx.F + fx[i][0];
74             int nxy = nx.S + fx[i][1];
75             if(nxx < 0 || nxx > 4 || nxy < 0 || nxy > 4 || mp[nxx][nxy] == 1 || vis[nxx][nxy])
76                 continue;
77             vis[nxx][nxy] = 1;
78             q.push(make_pair(nxx,nxy));
79             bj[nxx*5+nxy].F = nx.F*5+nx.S;
80             bj[nxx*5+nxy].S.F = nxx, bj[nxx*5+nxy].S.S = nxy;
81         }
82     }
83     int nex = 24;
84     /* //这是用栈模拟的方式
85     stack<int>p;
86     while(nex){
87         p.push(nex);
88         nex = bj[nex].F;
89     }
90     p.push(0);
91     while(!p.empty()){
92         nex = p.top();
93         p.pop();
94         cout << "(" << bj[nex].S.F << ", " << bj[nex].S.S << ")"<< endl;
95     }
96     */
97     while(1){  //反向输出到ostringstream中
98         //cout << nex << endl;
99         if(nex == 0){
100             outt << ")" << bj[nex].S.S << " ," << bj[nex].S.F << "(";
101             break;
102         }
103         outt << ")" << bj[nex].S.S << " ," << bj[nex].S.F << "(" << "\n";
104         nex = bj[nex].F;
105     }
106
107 }
108
109 int main(){
110     ios_base::sync_with_stdio(false);
111     cout.tie(0);
112     cin.tie(0);
113     fill(vis[0],vis[0]+5*5,0);
114     for(int i = 0; i < 5; i++){
115         for(int j = 0; j < 5; j++){
116             cin>>mp[i][j];
117         }
118     }
119     bfs();
120     string s = outt.str();
121     reverse(s.begin(),s.end());  //再次逆序
122     cout << s << endl;
123
124     return 0;
125 }

|
3月前
|

【算法入门&搜索法】走迷宫|单源最短路径1
【算法入门&搜索法】走迷宫|单源最短路径1
48 0
|
3月前
DFS：迷宫搜索实践
DFS：迷宫搜索实践
23 1
|
4月前
|

86 0
|
4月前
|

77 0
|
4月前
|

76 0
|
4月前
|

LeetCode：搜索二维矩阵题解

80 0
|
7月前
|

【每日算法】 搜索与回溯算法（简单）

43 0
|
7月前
|

【每日算法】搜索与回溯算法（简单）

38 0
|
9月前
【CCCC】L3-008 喊山 (30分)，BFS搜索最长路，水题
【CCCC】L3-008 喊山 (30分)，BFS搜索最长路，水题
49 0
|
10月前
|

LDUOJ——I. 买汽水（折半搜索+双指针）
LDUOJ——I. 买汽水（折半搜索+双指针）
55 0