State graph

A state graph is what you search when the position alone does not decide the next moves: you may carry a key, face a direction or hold some water in two jugs. Each vertex is a position together with that extra information, and BFS or Dijkstra's algorithm runs on it unchanged.

Explanation

A small flat has 4 rooms. Room 1 opens into room 2, and room 2 opens into rooms 3 and 4. The door between rooms 2 and 3 is locked, and its key lies in room 4. How many doors do you pass to get from room 1 to room 3?

Fig. 1. The key lies in room 4, and the door from room 2 to room 3 is locked.

You go to room 2, fetch the key from room 4, come back to room 2 and open the locked door: 4 doors. The route passes room 2 twice, first without the key and then with it. A search that gives each room one number visits room 2 only once, so it has to handle that second visit somehow.

A house with more rooms gives more ways to the key and back. This one has 7 rooms and 7 doors. The door between rooms 4 and 7 is locked, the key lies in room 6, and we look for the fewest doors from room 1 to room 7.

Fig. 2. Find the fewest doors from room 1 to room 7. The key to the locked door lies in room 6.

There are several routes to room 6 and several from it, and you have to decide where to pick up the key on the way.

A first try is to run a breadth-first search over the rooms as usual, with one key for the whole search: once the search has found the key, the locked door opens. Room 6 gets 2, so the key is found early. When room 4 is taken from the queue with 3, the key has been found, so the locked door opens and room 7 gets 4 (Fig. 3).

Fig. 3. The numbers of the search with one key for the whole search. Room 7 gets 4 from the red route.

But the red route never enters room 6, so nobody walking it has the key. The real answer is the blue route through room 6: 5 doors.

Room 3 is reached twice: along the corridor without the key after 2 doors, and from room 6 with the key after 3 doors. Only the second can open the locked door, so the two arrivals need two numbers.

So describe each situation by two things: the room, and whether you carry the key. Such a description, everything you need to know to continue, is a state. Picture two copies of the house. The top copy is the house without the key, and the locked door is missing from it. The bottom copy is the house with the key, where every door opens. Room 6 appears only in the bottom copy, because whoever enters it picks up the key. So the doors into room 6 lead from the top copy down to the bottom one, and nothing leads back up, because you keep the key.

Fig. 4. Entering room 6 moves you down. No edge leads back up.

Every state has its own number, and a plain BFS on this bigger graph is right. A graph whose vertices are states and whose edges are moves is a state graph, and the search on it is BFS over states.

With one key you could also run one BFS to the key and a second one from it. The state graph does the same in one search, and it still works when there is no such split: several keys, a direction you face, the water in two jugs.

The start state, room 1 without the key, gets 0 and joins the queue.

Room 1 without the key is taken from the front of the queue.

Room 2 without the key is reached from room 1 without the key and gets 0 + 1 = 1.

Room 5 without the key is reached from room 1 without the key and gets 0 + 1 = 1.

Room 2 without the key is taken from the front of the queue.

Room 3 without the key is reached from room 2 without the key and gets 1 + 1 = 2.

Room 5 without the key is taken from the front of the queue.

Room 6 with the key is reached from room 5 without the key and gets 1 + 1 = 2. Entering room 6 picks up the key.

Room 3 without the key is taken from the front of the queue.

Room 4 without the key is reached from room 3 without the key and gets 2 + 1 = 3.

Room 6 with the key is taken from the front of the queue.

Room 5 with the key is reached from room 6 with the key and gets 2 + 1 = 3.

Room 3 with the key is reached from room 6 with the key and gets 2 + 1 = 3.

Room 4 without the key is taken from the front of the queue.

Room 5 with the key is taken from the front of the queue.

Room 1 with the key is reached from room 5 with the key and gets 3 + 1 = 4.

Room 3 with the key is taken from the front of the queue.

Room 2 with the key is reached from room 3 with the key and gets 3 + 1 = 4.

Room 4 with the key is reached from room 3 with the key and gets 3 + 1 = 4.

Room 1 with the key is taken from the front of the queue.

Room 2 with the key is taken from the front of the queue.

Room 4 with the key is taken from the front of the queue.

Room 7 with the key is reached from room 4 with the key and gets 4 + 1 = 5.

Room 7 with the key is taken from the front of the queue.

The queue is empty. Room 7 was reached only with the key, with 5, along the blue route through room 6.

1/25

Fig. 5. BFS over states. Green states are taken, and light blue states wait in the queue below.

Room 7 is reached only with the key. The run reached 12 of the 14 states: room 6 and room 7 without the key never occur.

Water jugs

Sometimes there is no map at all. You have two empty jugs of 3 and 5 litres and a tap. In one move you can fill a jug from the tap, empty a jug, or pour one jug into the other until the first is empty or the second is full. How do you measure exactly 4 litres?

Here a state is the pair of amounts: the litres in the small jug and the litres in the big jug. There are 4 · 6 = 24 pairs, and each of the six moves leads from one pair to another. BFS from the pair (0, 0) reaches 16 of the 24 pairs, and 4 litres first appear in the pair (3, 4), 3 litres in the small jug and 4 in the big one, after 6 moves. Pairs with both jugs partly full never appear, because every move leaves one of the jugs empty or full.

The route: fill the big jug, pour it into the small one, empty the small one, pour the 2 litres left into it, fill the big jug, and top up the small jug from it, which leaves 4 litres in the big jug.

Fig. 6. The pairs reached after 0, 1, 2, … moves.

Implementation

In the code, a room is a vertex and a door is an edge. A state is a pair (v, k): room v, and k = 1 if the key is carried, k = 0 if not. d[v][k] is the fewest doors to reach state (v, k) from the start, or -1 if it is not reached. The house is an adjacency list of pairs (neighbour, locked), and the queue holds states.

The state graph is never stored: when a state is taken, its moves are worked out from the house.

1. Choose the state: (v, k), the room and whether the key is carried.

2. List the moves: from (v, k) through each door of room v to a room u, except the locked door when k == 0. The new state is (u, 1) if k == 1 or u == key, and (u, 0) otherwise. In the house, from (5, 0) the door to room 6 gives (6, 1), and from (4, 0) the locked door to room 7 is skipped.

3. Search: BFS over states. Fill d with -1 and give the start state 0. Take the next state (v, k) from the queue. For each move to a state (u, nk) with d[u][nk] == -1, mark it: set d[u][nk] = d[v][k] + 1 and push it.

4. Read the answer: the smaller of d[t][0] and d[t][1] that is not -1, or -1 if both are. For the house, d[7][0] == -1 and d[7][1] == 5.

The program reads n and m, then m doors u v c, with c = 1 for the locked door and c = 0 for the others. The last line is the start room s, the target room t and the key room key. It prints the fewest doors from s to t, or -1. For the house the input is:

7 7
1 2 0
2 3 0
3 4 0
4 7 1
1 5 0
5 6 0
3 6 0
1 7 6

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);   // (neighbour, locked)
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    int s, t, key;
    cin >> s >> t >> key;

    // choose the state: (room v, k), k = 1 if the key is carried
    vector<vector<int>> d(n + 1, vector<int>(2, -1));
    queue<pair<int, int>> q;

    // search: initialise
    int k0 = (s == key) ? 1 : 0;
    d[s][k0] = 0;
    q.push({s, k0});

    while (!q.empty()) {
        // search: take the next state
        auto [v, k] = q.front();
        q.pop();

        // list the moves: every door that is open in this state
        for (auto [u, locked] : adj[v]) {
            if (locked && k == 0) continue;          // locked door, no key
            int nk = (k == 1 || u == key) ? 1 : 0;   // entering the key room takes the key
            if (d[u][nk] == -1) {
                // mark it
                d[u][nk] = d[v][k] + 1;
                q.push({u, nk});
            }
        }
    }

    // read the answer: the better of the two states of room t
    int ans = -1;
    for (int k = 0; k < 2; k++)
        if (d[t][k] != -1 && (ans == -1 || d[t][k] < ans)) ans = d[t][k];
    cout << ans << '\n';
}

There are $2n$ states, each taken once, and taking (v, k) checks the doors of room v, so the time and memory are O(n + m). In general, the time is the number of states times the number of moves from a state.

A direction in the state

Suppose that in a grid maze you may only go straight or turn right. Facing east in a cell and facing north in the same cell are different states, because they allow different next cells. So the state is (cell, direction): 4 states per cell, 4 \cdot R \cdot C states for a grid of R rows and C columns, and d[r][c][dir]. A state of several numbers can also be packed into one integer, such as (r * C + c) * 4 + dir, when one flat array is easier.

Several keys

With K kinds of keys, the state is the room and the set of keys carried. The set is a bit mask, an integer mask whose bit j is 1 if key j is carried. There are n \cdot 2^K states, and the time is O((n + m) \cdot 2^K).

The first line is now n m K. A door u v c has c = 0 if it is open and c = j + 1 if key j opens it. Then come K rooms, where keys 0, 1, …, K - 1 lie, and the last line is s t. The array keyIn[v] is the mask of the keys lying in room v. Only these lines change:

// read: adj[u].push_back({v, c - 1}), so j = -1 for an open door
vector<int> keyIn(n + 1, 0);
for (int j = 0; j < K; j++) {
    int r;
    cin >> r;
    keyIn[r] |= 1 << j;
}

// choose the state: (room v, set of keys mask)
vector<vector<int>> d(n + 1, vector<int>(1 << K, -1));

// search: initialise
d[s][keyIn[s]] = 0;
q.push({s, keyIn[s]});

// list the moves
for (auto [u, j] : adj[v]) {
    if (j >= 0 && !(mask >> j & 1)) continue;   // no key j
    int nmask = mask | keyIn[u];                 // take the keys in room u
    if (d[u][nmask] == -1) {
        // mark it
        d[u][nmask] = d[v][mask] + 1;
        q.push({u, nmask});
    }
}

// read the answer: the best d[t][mask] over all masks
int ans = -1;
for (int mask = 0; mask < (1 << K); mask++)
    if (d[t][mask] != -1 && (ans == -1 || d[t][mask] < ans)) ans = d[t][mask];

Moves with different costs

When moves cost different amounts, keep the same states and replace the queue with a priority queue: this is Dijkstra's algorithm over states. For example, cities are joined by roads, each city sells fuel at its own price per litre, and the tank holds at most c litres. The state is (city, litres in the tank), (v, f): n \cdot (c + 1) states. Buying one litre is a move from (v, f) to (v, f + 1) that costs the price in city v: in city 1 with an empty tank, buying a litre at price 3 leads to (1, 1) and costs 3. Driving a road of length len is a move from (v, f) to (u, f - len) that costs nothing, allowed when f >= len. The cheapest trip is the smallest d[t][f] among the states of the target city t.

Correctness proof

A route through the house that never passes the locked door without the key is a path in the state graph with the same number of doors, and the other way round.

Along a route, whether you carry the key is decided by the route itself: you carry it from the moment the route first enters room 6. So each room on the route becomes exactly one state, and each door becomes one edge: an edge inside one of the copies, or an edge down at room 6. The locked door is an edge only in the bottom copy, so a path in the state graph never passes it without the key. In the other direction, reading only the rooms of a path in the state graph gives a route through the house that obeys the lock.

The state graph is an ordinary graph in which every edge counts as one door, so BFS gives each state the fewest edges from the start state. By the correspondence, d_{v,k}, the number the program keeps in d[v][k], is the fewest doors of a valid route that ends in state (v, k). Every route to room $t$ ends in one of the states $(t,0)$ and $(t,1)$, so the answer is the smaller of d_{t,0} and d_{t,1}.

This needs the doors open from a state to depend only on the state. One key for the whole search breaks it: in Fig. 3 the locked door opens from room 4 because another route found the key, and room 7 gets 4 instead of 5.

Fig. 7. A route through the house is a path in the state graph with the same number of doors. The blue route goes down to the bottom copy at room 6.

Common mistakes

• One number per room while the queue carries the key, so an arrival with the key is skipped at a room already reached without it. Keep one number per state, d[v][k].

• One key for the whole search, a variable haveKey that becomes true once room 6 is taken, as in Fig. 3. The key belongs to a route, so put it in the state, (v, k).

• Reading the answer from one copy only, such as printing d[t][1] when the target is closer without the key. Take the smallest number over all states of the target, skipping $-1$.

• Putting too much into the state, such as the number of doors walked, so that no state ever repeats and the search never ends when the target can't be reached. Keep only what decides the next moves.

Similar algorithms

BFS over rooms or cells is enough when the position alone decides the moves. If two arrivals at the same cell can continue differently, you need states.

Dijkstra's algorithm runs on the same states when moves cost different amounts, such as buying fuel.

0-1 BFS runs on them when every move costs 0 or 1, as with (cell, direction) when going straight is free and a turn costs 1.

Multi-source BFS puts several start vertices at distance 0. On a state graph it works the same: for example, when the start cell may face any of four directions, all four start states get 0.

Dynamic programming also works on states. When moves never lead back to an earlier state, the states can be filled in order without a queue.

Practice