Codeforces 877D - Olya and Energy Drinks

发表于 分类于 Disqus：

链接

传送门

题意

给出\(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;
}
相关文章