Codeforces 877D - Olya and Energy Drinks

链接

传送门

题意

给出$n \times m(1 \leq n, m \leq 1000)$的地图(有障碍物)、起点和终点,每秒最多向一个方向走$k(1 \leq k \leq 1000)$步,问最少多少秒能从起点走到终点,无解输出-1。

思路

从起点开始BFS,每次向同一个方向扩展$k$步,由于每次可以走多步,所以可能出现路径交叉,多次访问同一个位置,这时不需要入队,只需要跳过重复位置继续进行后续的扩展。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1010;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
char s[maxn][maxn];
int vis[maxn][maxn];
queue<pii> q;
int main() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i) {
scanf("%s", s[i] + 1);
}
int ax, ay, bx, by;
scanf("%d%d%d%d", &ax, &ay, &bx, &by);
memset(vis, -1, sizeof vis);
vis[ax][ay] = 0;
q.push(make_pair(ax, ay));
while (!q.empty()) {
pii u = q.front();
if (u.X == bx && u.Y == by) {
break;
}
q.pop();
for (int i = 0; i < 4; ++i) {
int x = u.X + dx[i], y = u.Y + dy[i], j = k;
while (j-- && s[x][y] == '.' && (vis[x][y] == -1 || vis[x][y] > vis[u.X][u.Y])) {
if (vis[x][y] == -1) {
q.push(make_pair(x, y));
}
vis[x][y] = vis[u.X][u.Y] + 1;
x += dx[i], y += dy[i];
}
}
}
printf("%d\n", vis[bx][by]);
return 0;
}

支付宝扫码领红包