P1126机器人搬重物 | Wuhaoda's Blog

P1126机器人搬重物

反思:

这题在图的处理上不一般
第一感觉是重新建图
但编程复杂度会很高
参照题解上一种很巧妙的办法
即:把机器人移到格子中去,类比它在格点上处理
还学会了这种图bfs时的判重方法: Hash x y

传送门:

https://www.luogu.org/problemnew/show/P1126

ac代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define C getchar()
#define For(a,b,c,d) for(register int a=b;a<=c;a+=d)
using namespace std;

struct pos {
int x, y, f, moveTime;
};

const int moveY[4] = {0, 1, 0, -1}, moveX[4] = {-1, 0, 1, 0};
int data[60][60];
int m, n, ans;
bool vis[20000];
queue<pos> que;

template <typename T>
inline void read(T &s) {
s = 0;
T f = 1;
char ch = C;
for (; ch > '9' || ch < '0'; ch = C)
if(ch == '-')
f = -1;
for (; ch >= '0' && ch <= '9'; ch = C)
s = (s << 1) + (s << 3) + (ch ^ 48);
s *= f;
}

inline bool judge(int x, int y) {
if(data[x][y + 1] || data[x + 1][y] || data[x + 1][y + 1] || data[x][y])
return 1;
return 0;
}

inline void init() {
read(n), read(m);
For(i, 1, n, 1)
For(j, 1, m, 1)
read(data[i][j]);

}

inline int Hash(int a, int b, int c) {
return c * 2700 + a * 51 + b;
}

inline void bfs() {
int x, y, tx, ty, f, d, moveTime, lx, ly;
char c;
read(x), read(y), read(tx), read(ty);
scanf("%c", &c);
switch(c) {
case 'N': f = 0;
break;
case 'E': f = 1;
break;
case 'S': f = 2;
break;
case 'W': f = 3;
break;
}
pos temp;
temp.x = x, temp.y = y, temp.f = f, temp.moveTime = 0;
que.push(temp);
while(!que.empty()) {
temp = que.front();
que.pop();
x = temp.x, y = temp.y, f = temp.f, d = Hash(x, y, f), moveTime = temp.moveTime;
if(x == tx && y == ty) {
printf("%d", moveTime);
exit(0);
}
if(vis[d])
continue;
vis[d] = 1;
++temp.moveTime;
temp.f = (f + 4 - 1) % 4;
que.push(temp);
temp.f = (f + 5) % 4;
que.push(temp);
temp.f = f;
For(i, 1, 3, 1) {
lx = x + moveX[f] * i, ly = y + moveY[f] * i;
if(lx <= 0 || ly <= 0 || lx >= n || ly >= m || judge(lx, ly))
break;
temp.x = lx;
temp.y = ly;
que.push(temp);
}
}
printf("-1");
}

int main() {
init();
bfs();
}