智能搬运机器人算法 (智能搬运机器人代码)

本来没啥好说的，但细节实在比较多，被坑了好多次。

1.首先输入的是格子图，需要转化成点图，具体操作是a[][i=ai-1北-1] =a[][ -1]=ali-1][i]=1

2.最坑的一个点在于，平时写宽搜的时候，遇到出边界或者不能访问的点时，都是直接进入下一层循环(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 'E':
78. st.dir = 0; break;
79. case 'S':
80. st.dir = 1; break;
81. case 'W':
82. st.dir = 2; break;
83. case 'N':
84. st.dir = 3; break;
85. }
86. bfs();
88. return 0;
89. }

注：本文转载自他处，如有侵权，请联系作者删除。