A - 深さ優先探索 - garakutagoya

DFS(深さ優先探索)の実装の練習です.蟻本を読みながらチャレンジ.

問題の説明

$H×W$ の大きさの迷路が与えられています.各々のマス目にはs,g,.,# のいずれかが与えられ,高橋君は自分のいる場所から上下左右に動く事が出来ますが,斜めに移動する事は出来ません.また,s,g,.,を通過する事は出来るが,# を通過する事は出来ません.

今,高橋君がsからスタートしたとき,上のルールに則ってg まで辿り着けるか答えなさい.

条件

$1≦H,W≦500$
s,g はそれぞれ1つだけ存在する.

考えた事

何はともあれ,まずは移動方法をどのように表すかを考える.斜めに移動できる場合は,

for(int i=-1;i<=1;i++) {
  for(int j=-1;j<=1;j++) {
    int nx = x + i;
    int ny = y + j;
  }
}

とすればよい.しかし,今回の場合は上下左右にしか動けないため,

vector<int> dx = { 1, 0, -1, 0 };
vector<int> dy = { 0, 1, 0, -1 };

このようにdx,dyベクトルを作り,iを変化させる事で上下左右の移動を表現した.

DFSは再帰函数で記す事が便利とされている.ならばこの場合,どのように再帰を終わらせる条件を作ればよいだろうか.

一つは当たり前であるが移動先が迷路の外である場合.もう一つは移動先が# である場合.ではこれだけでよいだろうか.

残念ながら,これだけでは足りないのである.これだと左右に行ったり来たりするような移動をした場合,再帰函数が無限に呼び出されてプログラムが終らなくなってしまう.そのため,今回は,

vector<vector<bool>> check(510, vector<bool>(510, false));

なる迷路に合わせたbool型の2次元配列を用意し,初期状態は全てfalseとし,現時点で高橋君が存在している場所をtrueとする.こうする事で移動先がtrueならばそこを通らないように条件節を作った.

まとめると,

場外に行かない
# を通らない
一度通った場所には戻らない(移動先がtrueでない)

として,ifの条件節を作り,これを満たした上下左右の移動のみを再帰して呼び出し,trueをつけて上下左右で上の条件を満たしているところにまたtrueをつけていく事を繰り返す再帰函数を作成した.

状態遷移は4方向の移動の4通り,DFSは各マスについて高々1度しか呼び出されない(既に呼び出した部分にはtrueがつく)ため,計算量は $O(4×H×W)=O(H×W)$ となり,条件を考えても十分間に合う.

求めたいのは,迷路をゴール出来るかどうかであるため,後はスタート地点からdfsを回し,ゴール地点の座標でのcheck配列がtrueかfalseとなるか調べればよい.

プログラム

#include <bits/stdc++.h>
using namespace std;
vector<int> dx = { 1, 0, -1, 0 };
vector<int> dy = { 0, 1, 0, -1 };

int H, W;

vector<string> field(H);
vector<vector<bool>> check(510, vector<bool>(510, false));

void dfs(int x, int y) {
    check.at(x).at(y) = true;
for(int i=0;i<4;i++) {
  int nx = x + dx.at(i);
  int ny = y + dy.at(i);
  if(nx < 0 || ny < 0 || nx >= H || ny >= W) {
    continue;
  }
  if(field.at(nx).at(ny) == '#') {
    continue;
  }
  if(check.at(nx).at(ny)) {
    continue;
  }
  dfs(nx, ny);
}
}

int main() {
  cin >> H >> W;
  field.resize(H);
  for(int i=0;i<H;i++) {
    cin >> field.at(i);
}
  int sx, sy, gx, gy;
  for(int i=0;i<H;i++) {
  for(int j=0;j<W;j++) {
  if(field.at(i).at(j) == 's') {
    sx = i;
    sy = j;
  }
    if(field.at(i).at(j) == 'g') {
    gx = i;
    gy = j;
    }
  }
  }
  dfs(sx, sy);
  if(check.at(gx).at(gy)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}