問題概要

$N \times M$ のグリッドがある。各マスは壁 (文字 '#') か通路 (文字 '.') かのいずれかである。グリッドの外周のマスはすべて壁であることが保証されている。

プレイヤーは最初、マス $(1, 1)$ にいる (0-indexed)。このマスは通路であることが保証されている。

プレイヤーは、今いる地点から上下左右のいずれかの方向を選択して、その方向に進むことを繰り返していく。ただし、一度進み始めると、壁にぶつかるまで止まることができない。

プレイヤーが触れることのできるマスの数の最大値を求めよ。

制約

$3 \le N, M \le 200$

考えたこと

ここでは DFS することにした。プレイヤーを上下左右に移動させていき、壁にぶつかって止まるたびに、再帰的に探索を繰り返していくこととする。

ここで気になるのは、プレイヤーが通過したマスは「もう探索済み」としてしまってよいかどうか。というのも、DFS において「探索済み」としたマスは、そこを起点として再帰的に探索を開始することはなくなるからだ。

結論から言えば、通過したマスはすべて「探索済み」としてしまってよい。なぜならば、プレイヤーが止まらずに通過したようなマスに対して、仮にその後プレイヤーが止まれることがあったとしても、もと来た道を引き返すか、すでに通過済みの方向にしか進むことができない。よって再帰的に探索を開始する意味はない。

計算量は、各マスに対する処理に $O(N + M)$ の計算量を要するため、全体で $O(NM(N+M))$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; ++i) cin >> S[i];
    
    // DFS
    vector<vector<bool>> seen(H, vector<bool>(W, false));
    auto dfs = [&](auto self, int x, int y) -> void {
        seen[x][y] = true;
        for (int dir = 0; dir < 4; ++dir) {
            int x2 = x, y2 = y;
            while (S[x2 + dx[dir]][y2 + dy[dir]] == '.') {
                seen[x2][y2] = true;
                x2 += dx[dir];
                y2 += dy[dir];
            }
            if (!seen[x2][y2]) {
                self(self, x2, y2);
            }
        }
    };
    dfs(dfs, 1, 1);
    
    int res = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (seen[i][j]) ++res;
        }
    }
    cout << res << endl;
}