k-tokitoh

2019-07-29

AtCoder Typical Contest 001 A

A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder

コード

他の回答をみつつ実装した。

#include<iostream>
#include<string>
using namespace std;
#define MAX_H 500
#define MAX_W 500

int h, w;
char maze[MAX_H][MAX_W];
bool visited[MAX_H][MAX_W];

# i,jを渡すと
# - そこからゴールに行けるならtrueを返す。
# - そこからゴールに行けるならvisited[i][j]をtrueにする。
bool search(int i, int j) {
  # マップの外側ならfalseを返す
  if (i<0 || h<=i || j<0 || w<=j) return false;
  # 壁ならfalseを返す
  if (maze[i][j] == '#') return false;
  # 訪問済みならfalseを返す
  if (visited[i][j]) return false;
  # ゴールならtrueを返す
  if (maze[i][j] == 'g') return true;

  # 訪問済みとしてマークする
  visited[i][j] = true;

  # 上下左右について再帰的にsearchを呼び出す
  return(
    search(i - 1, j    ) ||
    search(i + 1, j    ) ||
    search(i    , j - 1) ||
    search(i    , j + 1)
  );
}

int main() {
  # 入力を受け取る
  int start[2];
  cin >> h >> w;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> maze[i][j];
      # スタートの位置も記録しておく
      if (maze[i][j] == 's') {
        start[0] = i;
        start[1] = j;
      }
      # 配列visitedを初期化しておく
      visited[i][j] = false;
    }
  }

  # 主要な処理
  string ret = (search(start[0], start[1]) == true) ? "Yes" : "No";

  cout << ret << endl;
}

学んだこと