Sliding Pieces

A bishop slides diagonally until it hits a wall. Sliding costs one move — but the slide can cover 1 cell or 50. This is the "inertia" mechanic: once you pick a direction, continuing is free. Turning costs you. The state needs to remember which way you're heading.

The Inertia Pattern

Many grid problems share this structure:

You move in a direction and slide until you stop.
Continuing in the same direction is free (cost 0).
Changing direction costs 1 (a new "move").

Standard BFS treats each cell as a node. That misses the direction information. The fix: expand the state to (row, col, direction). Then 0-1 BFS handles the rest.

💡 Key insight. When continuing is free and turning costs 1, you're counting the number of direction changes, not the number of cells traversed. Direction becomes a first-class dimension of your state.

AtCoder abc246_e — Bishop 2

Problem. An \(N \times N\) board with obstacles. A bishop starts at \((s_r, s_c)\) and wants to reach \((g_r, g_c)\). The bishop moves by choosing a diagonal direction and sliding any number of cells. Each such slide is one move. Minimize the number of moves.

Constraints. \(N \leq 1500\). The board has up to \(N^2 = 2.25 \times 10^6\) cells.

Modeling the Graph

Ice sliding puzzle: slide until hitting wall at zero cost, change direction costs 1

State: \((r, c, d)\) where \(d \in \{0,1,2,3\}\) is the diagonal direction (NE, NW, SW, SE).

Edges:

Continue sliding in direction \(d\): move to \((r + dr_d, c + dc_d, d)\) with cost 0.
Start a new direction \(d'\): stay at \((r, c, d')\) with cost 1.

Total nodes: \(4N^2\). Each node has at most 1 cost-0 edge (slide one more cell) and 3 cost-1 edges (change direction). Total edges: \(O(N^2)\).

Why Not Naive BFS?

A tempting approach: for each cell, BFS with one edge per entire slide. But each slide can visit up to \(N\) cells, giving \(O(N)\) edges per node and \(O(N^3)\) total — too slow for \(N = 1500\).

The 0-1 BFS formulation has \(O(N^2)\) edges total. Each cell-direction pair has exactly one "continue" neighbor. That's the key speedup.

⚠ Gotcha. Without the direction in the state, you can't distinguish "arriving at (3,3) heading NE" from "arriving at (3,3) heading SW." These have different costs for reaching (3,3)'s neighbors because continuing NE is free but switching to SW costs a move.

Full Trace

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

. . . . .
. . # . .
. # . . .
. . . . .
. . . . .

Bishop at \((0,0)\), heading SE (direction 3):

Step	Pop	Action
1	\((0,0,\text{SE})\)	Slide SE to \((1,1)\). Continue cost=0
2	\((1,1,\text{SE})\)	\((2,2)\) is `.`. Slide to \((2,2)\), cost=0
3	\((2,2,\text{SE})\)	Slide to \((3,3)\), cost=0
4	\((3,3,\text{SE})\)	Slide to \((4,4)\), cost=0

Answer: 1 move. The bishop slides the entire diagonal in a single move. All the intermediate cost-0 transitions are part of one continuous slide.

Now try start = \((0,0)\), goal = \((0,4)\):

Step	Pop	Cost	Action
1	\((0,0,\text{SE})\)	0	Slide to \((1,1)\), \((2,2)\), \((3,3)\), \((4,4)\). All cost 0
2	\((4,4,\text{SE})\)	0	Wall. Change to NE: \((4,4,\text{NE})\), cost=1
3	\((4,4,\text{NE})\)	1	Slide to \((3,5)\)? Out of bounds. Try NW
4	\((4,4,\text{NW})\)	1	Slide to \((3,3)\), already visited cheaper
...	...	...	Eventually finds path via \((2,2) \to\) NE \(\to (0,4)\)

Answer: 2 moves. SE to \((2,2)\), then NE to \((0,4)\).

Solution

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

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

    // Directions: NE, NW, SW, SE
    int dr[] = {-1, -1, 1, 1};
    int dc[] = {1, -1, -1, 1};

    // dist[r][c][d] = min moves to reach (r,c) heading direction d
    vector<vector<array<int,4>>> dist(N, vector<array<int,4>>(N));
    for (auto& row : dist)
        for (auto& cell : row)
            cell.fill(INT_MAX);

    deque<tuple<int,int,int>> dq;
    for (int d = 0; d < 4; d++) {
        dist[sr][sc][d] = 0;
        dq.push_back({sr, sc, d});
    }

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

        // Continue same direction: cost 0
        int nr = r + dr[d], nc = c + dc[d];
        if (nr >= 0 && nr < N && nc >= 0 && nc < N
            && grid[nr][nc] == '.'
            && cur < dist[nr][nc][d]) {
            dist[nr][nc][d] = cur;
            dq.push_front({nr, nc, d});
        }

        // Change direction at current cell: cost 1
        for (int nd = 0; nd < 4; nd++) {
            if (nd == d) continue;
            if (cur + 1 < dist[r][c][nd]) {
                dist[r][c][nd] = cur + 1;
                dq.push_back({r, c, nd});
            }
        }
    }

    int ans = INT_MAX;
    for (int d = 0; d < 4; d++)
        ans = min(ans, dist[gr][gc][d]);
    cout << (ans == INT_MAX ? -1 : ans) << endl;
}

💡 Key insight. The answer is min over all 4 directions of dist[gr][gc][d]. The goal cell can be reached from any direction — we don't care which one, just the cheapest.

Typical90 #43 — Maze Challenge with Lack of Sleep

Problem. Same inertia mechanic, but on a standard grid with 4 cardinal directions (up/down/left/right). Start at \((r_s, c_s)\), reach \((r_g, c_g)\). Each "step" chooses a direction and slides until hitting a wall. Minimize the number of steps.

This is identical to Bishop 2 but with cardinal directions instead of diagonals. The state is \((r, c, d)\) with \(d \in \{N, S, E, W\}\).

// Directions: N, S, E, W
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, 1, -1};

// Everything else is identical to Bishop 2

The pattern is the same. The only difference is the direction vectors.

The Pruning That Prevents TLE

Without careful pruning, 0-1 BFS on sliding pieces can degrade. Here's why and how to fix it.

The danger: A cell \((r,c)\) can be pushed to the deque many times — once for each direction, and re-pushed if a cheaper path is found. If you process a cell-direction pair that's already been finalized at a lower cost, you waste time re-sliding through cells you've already covered.

The fix: The cur < dist[nr][nc][d] check before pushing handles this. Once dist[r][c][d] is settled at the minimum, any future pop with a higher value gets skipped because it can't improve any neighbor.

⚠ Gotcha. If you forget the direction dimension and use dist[r][c] alone, you'll overwrite a cell's distance when it's reached from a different direction. This corrupts the BFS and gives wrong answers.

The Inertia Mental Model

Think of it as physics. An object in motion tends to stay in motion. Changing direction requires energy (cost 1). The state encodes the object's velocity, not just its position.

This pattern recurs throughout competitive programming:

Sliding puzzles (ice floors, bishops, rooks)
Laser reflection (continue straight = free, mirror = cost)
Robot navigation (turning costs fuel, driving is cheap)

Whenever the problem says "continuing is free but starting costs 1," add direction to state and use 0-1 BFS.

Exercises

Rook variant. A rook slides horizontally or vertically. Same inertia rules. How many states does the graph have for an \(N \times N\) board?
Edge count. In the Bishop 2 formulation, prove the total number of edges is \(O(N^2)\), not \(O(N^3)\).
No-inertia baseline. Solve Bishop 2 without the inertia trick (BFS where each slide is one edge scanning up to \(N\) cells). What's the time complexity? Why is it too slow?

Problems

Problem	Link	Difficulty
AtCoder abc246_e — Bishop 2	atcoder.jp/contests/abc246/tasks/abc246_e	Medium
Typical90 #43 — Maze Challenge	atcoder.jp/contests/typical90/tasks/typical90_aq	Medium
LC 1284 — Minimum Number of Flips	leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix	Hard