BFSを繰り返すときに訪問済みかを記録する配列を毎回初期化しなくて良くするアレ

あまり広まっておらず知る人ぞ知るテクみたいになってる気がしたので。

グリッド上でBFSをするときに、単純に書くとこのような感じになると思います。

bool bfs(const vector<vector<int>>& grid, int r, int c) {
    vector<pair<int, int>> queue = { {r, c} };
    vector<vector<bool>> visited(H, vector<bool>(W));
    visited[r][c] = true;
    int qi = 0;
    while (qi < queue.size()) {
        auto [cr, cc] = queue[qi];
        for (int i = 0; i < 4; ++i) {
            int nr = cr + DR[i];
            int nc = cc + DC[i];
            if (nr < 0 || H <= nr || nc < 0 || W <= nc) continue;
            if (visited[nr][nc] || grid[nr][nc] == WALL) continue;
            if (grid[nr][nc] == GOAL) return true;
            queue.emplace_back(nr, nc);
            visited[nr][nc] = true;
        }
        qi++;
    }
    return false;
}

とりあえず、毎回メモリ確保するのを避けるため visited を毎回作らないようstaticにしましょう。

bool bfs(const vector<vector<int>>& grid, int r, int c) {
    vector<pair<int, int>> queue = { {r, c} };
    static vector<vector<bool>> visited(H, vector<bool>(W));
    for (int i = 0; i < H; ++i) {
        fill(visited[i].begin(), visited[i].end(), false);
    }
    visited[r][c] = true;
    // 以下略
}

同じBFSを何回もやるのだけど、ほとんどのケースではグリッド全体を見ることなく探索が終了するというシチュエーションがしばしばあります。
そのような場合、 visited の初期化に無視できない時間がかかり、削減したくなります。

「今回が何回目のBFSか」（下のコード中でいう bfs_cnt ）を保持して、 visited を「今回のBFSで訪問したかどうか」のboolではなく、「直近で何回目のBFSで訪問したか」のintで持つようにすると、BFSのたびにH*Wの配列を初期化する必要がなくなります。

bool bfs(const vector<vector<int>>& grid, int r, int c) {
    vector<pair<int, int>> queue = { {r, c} };
    static vector<vector<int>> visited(H, vector<int>(W));
    static int bfs_cnt = 0;
    bfs_cnt++;
    visited[r][c] = bfs_cnt;
    int qi = 0;
    while (qi < queue.size()) {
        auto [cr, cc] = queue[qi];
        for (int i = 0; i < 4; ++i) {
            int nr = cr + DR[i];
            int nc = cc + DC[i];
            if (nr < 0 || H <= nr || nc < 0 || W <= nc) continue;
            if (visited[nr][nc] == bfs_cnt || grid[nr][nc] == WALL) continue;
            if (grid[nr][nc] == GOAL) return true;
            queue.emplace_back(nr, nc);
            visited[nr][nc] = bfs_cnt;
        }
        qi++;
    }
    return false;
}