Skip to content

0-1 BFS

Dijkstra costs you \(O((V+E) \log V)\). When every edge weight is either 0 or 1, you're paying a logarithmic tax for nothing. A deque replaces the priority queue, the log factor vanishes, and you get \(O(V+E)\) shortest paths. This is 0-1 BFS — the single most useful trick in competitive programming grids.

Why Dijkstra Overpays

0-1 BFS vs Dijkstra: deque vs heap, O(V+E) vs O((V+E)logV)

Dijkstra uses a priority queue to always process the minimum-distance node. But when weights are only 0 and 1, the distances in the queue only ever span two consecutive values: the current minimum \(d\) and \(d+1\).

A deque exploits this. Cost-0 edges push to the front (same distance tier). Cost-1 edges push to the back (next tier). The front of the deque is always the global minimum. No heap needed.

Key insight. The deque acts as a two-tier bucket queue. Front = current distance. Back = current distance + 1. This sorted invariant holds because we only ever add 0 or 1 to the current distance.

The Algorithm

0-1 BFS: weight-0 edges push to front of deque, weight-1 to back

  1. Set dist[source] = 0, all others to \(\infty\).
  2. Push source to the deque.
  3. Pop from the front. If stale, skip.
  4. For each edge: if cost is 0, push neighbor to front. If cost is 1, push to back.
  5. Repeat until deque is empty.
deque<int> dq;
vector<int> dist(n, INT_MAX);
dist[src] = 0;
dq.push_back(src);

while (!dq.empty()) {
    int u = dq.front(); dq.pop_front();
    for (auto [v, w] : adj[u]) {  // w is 0 or 1
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            if (w == 0) dq.push_front(v);
            else         dq.push_back(v);
        }
    }
}

Gotcha. You still need the stale-entry check — or equivalently, the dist[u] + w < dist[v] guard. Without it, you'll process nodes multiple times and the invariant breaks.

When to Use What

Condition Algorithm Time
All weights = 1 BFS \(O(V+E)\)
All weights in 0-1 BFS \(O(V+E)\)
All weights \(\geq 0\) Dijkstra \(O((V+E) \log V)\)
Negative weights Bellman-Ford \(O(VE)\)

0-1 BFS sits in the sweet spot. The moment you see a problem with exactly two cost levels — one of which is "free" — reach for the deque.

AtCoder abc176_d — Wizard in Maze

Problem. An \(H \times W\) grid. # is wall, . is open. A wizard starts at \((s_r, s_c)\) and wants to reach \((g_r, g_c)\). Each turn, the wizard either:

  • Walks to an adjacent cell (up/down/left/right) — costs 0 magic.
  • Warps to any cell in a \(5 \times 5\) area centered on the current position — costs 1 magic.

Minimize total magic used. Print \(-1\) if impossible.

Mapping to 0-1 BFS. Walking is a cost-0 edge. Warping is a cost-1 edge. The graph has \(H \times W\) nodes, each with 4 cost-0 neighbors and up to 24 cost-1 neighbors.

Full Trace

Grid (\(5 \times 5\)), start = \((0,0)\), goal = \((4,4)\):

. . # . .
. # # # .
. # . # .
. # . . .
. . . # .
Step Pop dist Deque (front → back)
Init — \((0,0)=0\), rest \(\infty\) \([(0,0)]\)
1 \((0,0)\) d=0 \((1,0)=0\), \((0,1)=0\) \([(1,0),(0,1)]\) + warp targets at d=1
2 \((1,0)\) d=0 \((2,0)=0\), \((3,0)=0\) \([(2,0),(3,0),(0,1), \ldots]\)
3 \((2,0)\) d=0 \((3,0)\) already 0 \([(3,0),(0,1),\ldots]\)
4 \((3,0)\) d=0 \((4,0)=0\) \([(4,0),(0,1),\ldots]\)
5 \((4,0)\) d=0 \((4,1)=0\) \([(4,1),(0,1),\ldots]\)
6 \((4,1)\) d=0 \((4,2)=0\) \([(4,2),(0,1),\ldots]\)
... ... ... ...
\((4,2)\) d=0 warp \((2,4)=1\) push back
\((2,4)\) d=1 \((3,4)\) is wall skip
warp from \((4,2)\) \((4,4)=1\) done

Answer: 1. The wizard walks along the left and bottom edges for free, then warps over the wall to reach \((4,4)\).

Solution

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

int main() {
    int H, W;
    cin >> H >> W;
    int sr, sc, gr, gc;
    cin >> sr >> sc >> gr >> gc;
    sr--; sc--; gr--; gc--;
    vector<string> grid(H);
    for (auto& s : grid) cin >> s;

    vector<vector<int>> dist(H, vector<int>(W, INT_MAX));
    deque<pair<int,int>> dq;
    dist[sr][sc] = 0;
    dq.push_back({sr, sc});

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!dq.empty()) {
        auto [r, c] = dq.front(); dq.pop_front();
        int d = dist[r][c];

        // Walk: cost 0
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < H && nc >= 0 && nc < W
                && grid[nr][nc] == '.' && d < dist[nr][nc]) {
                dist[nr][nc] = d;
                dq.push_front({nr, nc});
            }
        }
        // Warp: cost 1
        for (int wr = r-2; wr <= r+2; wr++) {
            for (int wc = c-2; wc <= c+2; wc++) {
                if (wr >= 0 && wr < H && wc >= 0 && wc < W
                    && grid[wr][wc] == '.' && d + 1 < dist[wr][wc]) {
                    dist[wr][wc] = d + 1;
                    dq.push_back({wr, wc});
                }
            }
        }
    }

    cout << (dist[gr][gc] == INT_MAX ? -1 : dist[gr][gc]) << endl;
}

AGC043-A — Range Flip Find Route

Problem. An \(H \times W\) grid of black (.) and white (#) cells. You move from \((1,1)\) to \((H,W)\) going only right or down. Before moving, you can flip contiguous rectangular regions. Each flip costs 1. Minimize the number of flips to create an all-white path.

Key reframing. You don't actually need to think about rectangles. Walking from a white cell to another white cell costs 0. Walking from a white cell to a black cell costs 1 (you need a new flip to start a white segment). Walking from black to black costs 0 (same flip covers it). Walking from black to white costs 0 (the flip ends).

So the cost of stepping from cell \((r,c)\) to \((r',c')\) is:

\[w = \begin{cases} 1 & \text{if } grid[r'][c'] = \text{black and } grid[r][c] = \text{white} \\ 0 & \text{otherwise} \end{cases}\]

That's a 0-1 BFS on a grid with only right/down moves.

Key insight. Each "entry into a black segment" costs exactly one flip. The number of flips equals the number of white-to-black transitions along the path. This converts a confusing geometry problem into a clean 0-1 BFS.

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

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    for (auto& s : grid) cin >> s;

    vector<vector<int>> dist(H, vector<int>(W, INT_MAX));
    deque<pair<int,int>> dq;
    dist[0][0] = (grid[0][0] == '#') ? 1 : 0;
    dq.push_back({0, 0});

    int dr[] = {1, 0};
    int dc[] = {0, 1};

    while (!dq.empty()) {
        auto [r, c] = dq.front(); dq.pop_front();
        int d = dist[r][c];
        for (int k = 0; k < 2; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= H || nc >= W) continue;
            int cost = (grid[nr][nc] == '#' && grid[r][c] == '.') ? 1 : 0;
            if (d + cost < dist[nr][nc]) {
                dist[nr][nc] = d + cost;
                if (cost == 0) dq.push_front({nr, nc});
                else           dq.push_back({nr, nc});
            }
        }
    }

    cout << dist[H-1][W-1] << endl;
}

The Deque Invariant — Why Correctness Holds

The deque always contains nodes at distances \(d\) and \(d+1\) for some current \(d\). All distance-\(d\) nodes sit at the front, all distance-\((d+1)\) nodes sit at the back.

When we pop a distance-\(d\) node and push a cost-0 neighbor, it goes to the front at distance \(d\). A cost-1 neighbor goes to the back at distance \(d+1\). The sorted order is preserved.

When all distance-\(d\) nodes are exhausted, the front becomes distance-\((d+1)\), and the window slides forward. This is exactly the BFS level-by-level processing, but with two levels active at once.

Gotcha. 0-1 BFS does NOT generalize to {0, 2} or {1, 2} weights. The deque trick requires one of the weights to be exactly 0. For {0, 1, 2, ...} weights, you need a full Dijkstra or a multi-bucket approach.

Exercises

  1. Verify the invariant. Trace through the Wizard in Maze example and confirm that the deque only ever contains nodes at two consecutive distance values.

  2. Counting cells. In the AGC043 problem, what's the maximum number of flips if the grid alternates black and white in a checkerboard pattern?

  3. Reverse thinking. In Wizard in Maze, what if warping were free and walking cost 1? How does the answer change?

Problems

Problem Link Difficulty
AtCoder abc176_d — Wizard in Maze atcoder.jp/contests/abc176/tasks/abc176_d Medium
AGC043-A — Range Flip Find Route atcoder.jp/contests/agc043/tasks/agc043_a Medium
LC 2290 — Minimum Obstacle Removal leetcode.com/problems/minimum-obstacle-removal-to-reach-corner Hard
LC 1368 — Minimum Cost to Make at Least One Valid Path leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid Hard