AtCoder Typical Contest 001 A

C++ AtCoder 深さ優先探索 SyncQiita

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;
}

学んだこと

  • 大筋としては単なる再帰なのだが、戻らないようにするために訪問済みかどうかという情報をメモ化しておく必要がある、っていうのがポイント。
  • cinで入力を受け取ってcharに入れる場合、ちゃんと1文字ずつ受け取ってくれるみたい。
  • array[i]は格納された中身を取り出すので、文字列と比較するときはarray[i] == "string"ではなくarray[i] == 'string'
  • search関数の中でmazeという配列を使わないといけないけど、mazeの大きさが具体的に決まるのはmain関数内で標準入力を受け取ってから。
    • => main関数の外側で予め十分に大きなサイズのmazeという配列をつくっておけばよい！