ARC031 B:埋め立て

またまたグラフ問題。

https://atcoder.jp/contests/arc031/tasks/arc031_2

迷路探索みたいな感じなのでしゃーなしにdfsで解いた。が、見るも無残なクソコードを量産し(当然バグってる)ACするまでに鬼のような時間がかかった。はあ…はあ…dfsめ…。

vector<string> g_graph(10);
const int dx[] = { 0,-1,1,0 };
const int dy[] = { -1,0,0,1 };
 
void dfs(int y, int x, vector<vector<bool>>& visited) {
    visited[y][x] = true;
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i], nx = x + dx[i];
        if (ny < 0 || ny >= 10 || nx < 0 || nx >= 10) {
            continue;
        }
        if (g_graph[ny][nx] == 'x') {
            continue;
        }
        if (visited[ny][nx]) {
            continue;
        }
        dfs(ny, nx, visited);
    }
}
 
bool go(int start_y, int start_x) {
    vector<vector<bool>> visited(10, vector<bool>(10, false));
    dfs(start_y, start_x, visited);
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (g_graph[i][j] == 'o' && visited[i][j] == false) {
                return false;
            }
        }
    }
    return true;
}
 
signed main() {
    for (int i = 0; i < 10; i++) {
        cin >> g_graph[i];
    }
    bool ok = false;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (go(i, j)) {
                ok = true;
            }
        }
    }
    string ans = ok ? "YES" : "NO";
    cout << ans << endl;
}

え〜このコードは何をしているかと言えば、

  • とりあえずグラフを受け取る。
  • 1マスずつ始点(埋立地候補)としてgo()関数を呼び出す。実際は海マス(‘x’マス)の場合だけ始点とすればよい。
  • go()関数ごとに探索済みグラフを生成。dfs()を呼び出す。
  • dfs()内部では、陸続きになっているマスを探索させる。
  • 探索が終了しgo()関数に処理が戻ってきた時には探索済みグラフが完成しているはずなので、陸マス(‘o’マス)のすべてが探索済みになっていればOK。でなければ、2〜5を繰り返す。

っていう感じ。

dfsだけならまだしも、それを呼び出す関数内部でまたさらに探索済みグラフを舐めているからTLEかますのではないか?と思ったが、実際はどのテストケースも1ms内で処理が終わっていた。

dfsは実装するのも難しければオーダーを見積もるのも難しい。