[AtCoder ABC311 D Grid Ice Floor] DFS, DP

(問題ページ) AtCoder ABC311 D Grid Ice Floor
https://atcoder.jp/contests/abc311/tasks/abc311_d

---

1.考え方

「入力例 1」の例を考えます。
DFSで探索します。

当初、2次元配列visitedを用意しておき、
　　値が1: そのマスを通過
　　値が2: そのマスで方向転換
という風にして、ステータスを管理しようと考えました。

しかしこの場合、値2を上書きしてしまう可能性があると気が付きました。
例えば以下のような場合に、上書きされます(たぶん)

BFSで探索すれば、上書きされないで済むのか？
と一瞬思いましたが、何とも言えませんでした。

そこで、新たに2次元配列checkedを用意し、

• 2次元配列visited
  　　値が0: 未探索
  　　値が1: マスを探索済み
• 2次元配列checked
  　　値が0: 未探索
  　　値が1: 方向転換した

とすることにしました

探索が終わった後に、2次元配列visitedの値1をカウントすれば、答えが求まります。

2.code

#include <iostream>
#include <vector>
#include <limits>
using namespace std;


int N, M;
int dr[] = {0, 0, 1,-1};
int dc[] = {1,-1, 0, 0};


void dfs(int direction, int r, int c, vector<string> &S, vector<vector<int>> &visited, vector<vector<int>> &checked) {
    visited[r][c] = 1;
    int nr = r + dr[direction];
    int nc = c + dc[direction];

    if (S[nr][nc] == '.') {  // 同じ方向に進む
        dfs(direction, nr, nc, S, visited, checked);

    } else {  // 方向転換する
        if (checked[r][c] == 0) {
            checked[r][c] = 1;
            for (int i = 1; i < 4; i++) {
                int nd2 = (direction + i) % 4;
                int nr2 = r + dr[nd2];
                int nc2 = c + dc[nd2];
                if (S[nr2][nc2] == '#') {
                    continue;
                }
                dfs(nd2, nr2, nc2, S, visited, checked);
            }
        }
    }
}


int main() {
    cin >> N >> M;

    vector<string> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }

    vector<vector<int>> visited(N, vector<int>(M, 0));
    vector<vector<int>> checked(N, vector<int>(M, 0));
    dfs(0, 1, 1, S, visited, checked);

    int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited[i][j]) {
                cnt++;
            }
        }
    }

    printf("%d\n", cnt);
}