Grid and State-Space Graphs

Grid BFS/DFS, islands, shortest path with obstacles, multi-source distance fields, flood fill, 8-direction movement, weighted grid paths, keys/doors states, and graph modeling for puzzles.

Teach how to encode a state such as (row, column, keysMask) and estimate the state-space size before selecting an algorithm.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

The run shows the bug the mask prevents. Without the key in the state, BFS marks the cells right of the start visited while it does not yet hold the key; after fetching the key on the left it cannot revisit them, so it reports the goal unreachable. With the mask, (0,3) without a key and (0,3) with a key are different states, and the shortest route — left to the key, back past the start, through the door and down to the goal — is found. Estimate the state count first: R·C·2^K is fine for small K but 30 key types would mean 2³⁰ masks per cell.

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

int main() {
    // collect key 'a' to open door 'A'; '@' start, '$' goal. The key lies behind the start.
    vector<string> g = {"a.@.#", "###A#", "....$"};
    int R = 3, C = 5, K = 1;
    int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    auto solve = [&](bool trackKeys) {
        int masks = trackKeys ? 1 << K : 1;
        vector<vector<vector<int>>> dist(R, vector<vector<int>>(C, vector<int>(masks, -1)));
        queue<tuple<int, int, int>> q;
        for (int r = 0; r < R; ++r) for (int c = 0; c < C; ++c) if (g[r][c] == '@') { dist[r][c][0] = 0; q.push({r, c, 0}); }
        vector<vector<int>> keysHeld(R, vector<int>(C, 0));          // used only by the mask-less version
        while (!q.empty()) {
            auto [r, c, state] = q.front(); q.pop();
            int keys = trackKeys ? state : keysHeld[r][c];
            if (g[r][c] == '$') return dist[r][c][state];
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                char ch = g[nr][nc];
                if (ch == '#') continue;
                if (ch >=
…

state space: 3 x 5 x 2^1 = 30 states
BFS over (row, col, keys): fewest moves to reach $ = 8
BFS over (row, col) only:  result = -1 (unreachable - cells were marked visited before the key was found)
islands: 4

Quiz

? Why must the BFS state include the key mask?
+ The same cell is a different situation with different keys; marking only the cell visited would block a needed revisit. :: State = (row, col, keys).
- To save memory. :: It uses more memory.
- Because doors move. :: They do not.
- It is optional. :: The answer would be wrong.

? How many states does a 1000 × 1000 grid with 6 key types have?
+ 64 million :: 10⁶ cells × 2⁶ masks.
- 6 million :: Masks multiply, they do not add.
- 1 million :: Ignores keys.
- 10⁹ :: No.

? Why use an explicit stack in the flood fill?
+ A large connected region would need very deep recursion :: Same O(R·C) time, no stack overflow.
- It finds more islands. :: Same answer.
- Recursion cannot flood fill. :: It can, if the region is small.
- To sort cells. :: No.