【题解】【洛谷P1126】 机器人搬重物

清月无梦

P1126 机械人搬重物

传收门

---

那讲题本来出啥好道的，但细节其实比力多，被坑了很多多少次。

• 起首输进的是格子图，需求转化成面图，具体操作是
  
  
  
• 最坑的一个面正在于，平常写宽搜的时分，碰到出鸿沟大概不克不及会见的面时，皆是间接进进下一层轮回(continue)，但正在那讲题中，因为能够走1~3步，那末当途径上呈现停滞时，则不克不及停止下一轮轮回，需求break。
  

代码：

1. #include <bits/stdc++.h>
2. #define MAX 55
3. using namespace std;
5. int mod(int x){
6.         return (x+4)%4;
7. }
9. struct pt{
10.         int x, y, dir, step;
11.         pt(){}
12.         pt(int a, int b, int c, int d):x(a), y(b), dir(c), step(d){}
13. };
15. const int movx[] = {0,1,0,-1}, movy[] = {1,0,-1,0};
16. int a[MAX][MAX];
17. bool vis[MAX][MAX][5];
18. int n, m;
19. pt st, ed;
21. void bfs(){
22.         queue<pt> q;
23.         bool flag = false;
24.         st.step = 0;
25.         q.push(st);
26.         vis[st.x][st.y][st.dir] = true;
27.         while(!q.empty()){
28.                 pt t = q.front();
29.                 q.pop();
30.                 if(t.x == ed.x && t.y == ed.y){
31.                         cout << t.step << endl;
32.                         flag = true;
33.                         break;
34.                 }
35.                 for(int i = 1; i <= 3; i++){
36.                         int u, v;
37.                         u = t.x + i*movx[t.dir];
38.                         v = t.y + i*movy[t.dir];
39.                         if(u<=0 || u>=n || v<=0 || v>=m || a[u][v] == 1){
40.                                 break;
41.                         }
42.                         if(vis[u][v][t.dir]){
43.                                 continue;
44.                         }
45.                         vis[u][v][t.dir] = true;
46.                         q.push(pt(u, v, t.dir, t.step+1));
47.                 }
48.                 if(!vis[t.x][t.y][mod(t.dir+1)]){
49.                         vis[t.x][t.y][mod(t.dir+1)] = true;
50.                         q.push(pt(t.x, t.y, mod(t.dir+1), t.step+1));
51.                 }
52.                 if(!vis[t.x][t.y][mod(t.dir-1)]){
53.                         vis[t.x][t.y][mod(t.dir-1)] = true;
54.                         q.push(pt(t.x, t.y, mod(t.dir-1), t.step+1));
55.                 }
56.         }
57.         if(!flag){
58.                 cout << -1 << endl;
59.         }
60. }
62. int main()
63. {
64.         cin >> n >> m;
65.         for(int i = 1; i <= n; i++){
66.                 for(int j = 1; j <= m; j++){
67.                         scanf("%d", &a[i][j]);
68.                         if(a[i][j] == 1){
69.                                 a[i-1][j-1] = a[i-1][j] = a[i][j-1] = 1;
70.                         }
71.                 }
72.         }
73.         cin >> st.x >> st.y >> ed.x >> ed.y;
74.         char c;
75.         cin >> c;
76.         switch(c){
77.                 case &#39;E&#39;:
78.                         st.dir = 0; break;
79.                 case &#39;S&#39;:
80.                         st.dir = 1; break;
81.                 case &#39;W&#39;:
82.                         st.dir = 2; break;
83.                 case &#39;N&#39;:
84.                         st.dir = 3; break;
85.         }
86.         bfs();
87.        
88.         return 0;
89. }

复造代码

 

免责声明：假如进犯了您的权益，请联络站少，我们会实时删除侵权内乱容，感谢协作！