题面
每个点拆成两个点,使用过跳跃和未使用过
bfs即可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
using namespace std;
int qx[2000010], qy[2000010], qw[2000010], head, tail;
int dis[1010][1010][2], h, w, d, r;
char mp[1010][1010];
int fx[4] = {1, -1, 0, 0}, fy[4] = {0, 0, 1, -1};
int main() {
scanf("%d%d%d%d", &h, &w, &d, &r);
for(int i = 0; i < h; i++) scanf("%s", mp[i]);
memset(dis, -1, sizeof dis);
head = tail = 0;
qx[0] = qy[0] = qw[0] = 0;
dis[0][0][0] = 0;
if(mp[0][0] == '#') return puts("-1"), 0;
while(head <= tail) {
// printf("%d %d %d\n", qx[head], qy[head], qw[head]);
for(int i = 0; i < 4; i++) {
int newx = qx[head] + fx[i], newy = qy[head] + fy[i];
if(newx >= 0 && newx < h && newy >= 0 && newy < w && dis[newx][newy][qw[head]] == -1 && mp[newx][newy] == '.') {
dis[newx][newy][qw[head]] = dis[qx[head]][qy[head]][qw[head]] + 1;
tail++;
qx[tail] = newx;
qy[tail] = newy;
qw[tail] = qw[head];
}
}
int newx = qx[head] + d, newy = qy[head] + r;
if(qw[head] == 0 && newx >= 0 && newx < h && newy >= 0 && newy < w && dis[newx][newy][1] == -1 && mp[newx][newy] == '.') {
dis[newx][newy][1] = dis[qx[head]][qy[head]][qw[head]] + 1;
tail++;
qx[tail] = newx;
qy[tail] = newy;
qw[tail] = 1;
}
head++;
}
printf("%d\n", (int)min((unsigned)dis[h - 1][w - 1][1], (unsigned)dis[h - 1][w - 1][0]));
return 0;
}