幅優先探索 動的計画法 atcoder

ABC007 C - 幅優先探索

ABC007 C - 幅優先探索
Feb. 2, 2020, 1:52 p.m.

目次

問題

https://atcoder.jp/contests/abc007/tasks/abc007_3

入力

$H W$
$sy sx$
$gy gx$
$c_{0,0} c_{0,1} ... c_{0,W-1}$
...
$c_{H-1,0} c_{H-1,1} ... c_{H-1,W-1}$.

  • $H$ - 迷路の高さ
  • $W$ - 迷路の幅
  • $sy sx$ - スタート地点の座標
  • $gy gx$ - ゴール地点の座標

出力

$(sx, sy)$から$(gx, gy)$に至る最短経路を出力する問題です.
上下左右に動くことが出来て、.は通ることが出来、#は通れません.

解説

最短経路と聞けばまっさきに幅優先探索が思い浮かびます.
幅優先探索では近い順に探索するので、最初にゴールを見つけた時に最短経路であることが保証されています.
すべてのマスを1回ずつ訪問するので計算量は$O(H W)$です.

スタート地点からの距離の計算には動的計画法の考え方を使用します.
迷路と同じサイズの配列を用意し、$\infty$で初期化します.
$\infty$というのは、距離としてありえない範囲での最小の値です.
今回は迷路のサイズは$50 \times 50$なので最大距離は約$2500$です.
なので$\infty = 3000$とします.
(大きすぎる値を設定しないのは計算時のオーバーフローを防ぐためです.)

スタート地点を距離$0$として、4近傍で未訪問(距離が$\infty$未満)の点に移動していきます.
距離は1つ移動するたびに前回いた点の距離に$+1$していきます.

訪問した点がゴールと等しければその点の距離を答えとします.

計算量

$$
O(H W)
$$

解答

今回迷路と距離は2次元配列ではなく1次元配列で表現しています.
2次元配列の方が直感的で分かりやすいですが、vectorを使った一次元配列にも以下のようなメリットがあります.

  • 1) vector.atではC言語の配列のインデックスアクセスと違い不正なインデックスアクセスをした時のエラーが分かりやすい.
  • 2) サイズと初期値を指定した初期化が簡単.

幅$W$の座標$(x, y)$には$vector.at(y*W+x)$でアクセス可能です.

 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
#define MAX_N 50
#define INFTY 3000

Int H, W, sx, sy, gx, gy;
char c_;
vector<bool> M(MAX_N * MAX_N, true);
vector<Int> dist(MAX_N * MAX_N, INFTY);

void input() {
  cin >> H >> W >> sy >> sx >> gy >> gx;
  sx--, sy--, gx--, gy--;
  loop(h,0,H) {
    loop(w,0,W) {
      cin >> c_;
      if (c_ == '#') M[h*W + w] = false;
    }
  }
}

Int bfs(Int sx, Int sy) {
  queue<Vector2> Q;
  dist[sy*W + sx] = 0;
  Q.push(Vector2(sx, sy));

  while (Q.size()) {
    Vector2 u = Q.front(); Q.pop();
    loop(dx,-1,2) {
      loop(dy,-1,2) {
        if (dx != 0 && dy != 0) continue;
        Vector2 next = u + Vector2(dx, dy);
        if (next.x < 0 || next.x >= W || next.y < 0 || next.y >= H) continue;
        if (!M.at(next.y*W+next.x)) continue;
        if (dist.at(next.y*W + next.x) < INFTY) continue;
        dist[next.y*W+next.x] = dist[u.y*W+u.x] + 1;
        if (next.x == gx && next.y == gy) {
          return dist[next.y*W+next.x];
        }
        Q.push(next);
      }
    }
  }

  return INFTY;
}

void solve() {
  cout << bfs(sx, sy) << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}