Skip to content

Direction and Momentum

Direction as state dimension: node expanded into 4 states per direction

Lesson 2 added direction to the state. Now we add remaining momentum — how many more cells you can slide before you must start a new stroke. This is a 4D state: (row, col, direction, remaining). The state space explodes, but pruning keeps it tractable.

AtCoder abc170_f — Pond Skater

Problem. A water strider on an \(H \times W\) grid of lily pads (.) and water (#). Each stroke, it picks one of 4 cardinal directions and moves 1 to \(K\) cells in that direction. All cells along the path must be lily pads. Minimize the number of strokes to go from \((s_r, s_c)\) to \((g_r, g_c)\).

Constraints. \(H, W \leq 1000\). \(K \leq 1000\).

The Naive Approach Fails

Treating each stroke as a BFS edge: from each cell, scan up to \(K\) cells in each of 4 directions. That's \(O(K)\) edges per cell, \(O(HWK)\) total. With \(H = W = K = 1000\), that's \(10^9\) — way too slow.

The Inertia Reformulation

Split each stroke into individual cell-to-cell steps:

  • Continue sliding in the current direction with remaining momentum: cost 0.
  • Start a new stroke in any direction: cost 1.

State: \((r, c, d, rem)\) where \(d\) is the direction and \(rem\) is remaining slides in this stroke.

But wait — \(H \times W \times 4 \times K = 4 \times 10^9\) states? That's too many.

The Pruning Trick

We don't actually need \(rem\) in the distance table. Define:

\[\text{dist}[r][c][d] = \text{minimum strokes to reach } (r,c) \text{ heading in direction } d\]

If we arrive at \((r,c)\) heading direction \(d\) with fewer strokes than the current best, we process it. Otherwise skip. The remaining slides \(rem\) is tracked in the deque entry but not in the distance table.

💡 Key insight. Two states \((r,c,d,3)\) and \((r,c,d,7)\) with the same stroke count are equivalent for future cost — more remaining slides is strictly better. So we only need the minimum stroke count per \((r,c,d)\), and we carry \(rem\) as metadata.

This brings the distance table down to \(H \times W \times 4\) — manageable.

Full Trace

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

. . . . .
. . # . .
. . . . .
. . . . .
Step Pop \((r,c,d,rem)\) Strokes Action
1 \((0,1,E,2)\) 1 Start stroke East from \((0,0)\). Arrive at \((0,1)\)
2 \((0,2,E,1)\) 1 Continue East, cost 0
3 \((0,3,E,0)\) 1 Continue East, cost 0. Momentum spent
4 \((1,0,S,2)\) 1 Start stroke South from \((0,0)\)
5 \((2,0,S,1)\) 1 Continue South, cost 0
6 \((3,0,S,0)\) 1 Continue South, cost 0
... ... ... Processing all cost-0 extensions first
7 \((0,3,E,0)\) 1 New stroke South: \((1,3,S,2)\), strokes=2
8 \((3,0,S,0)\) 1 New stroke East: \((3,1,E,2)\), strokes=2
9 \((3,1,E,1)\) 2 Continue East: \((3,2,E,0)\), cost 0
10 \((3,2,E,0)\) 2 New stroke East: \((3,3,E,2)\), strokes=3
11 \((3,3,E,1)\) 3 Continue East: \((3,4,E,0)\), cost 0

Answer: 3 strokes. South 3 to \((3,0)\), East 3 to \((3,3)\)... but \((3,3)\) costs a new stroke at step 10. Optimal: East 3 to \((0,3)\), South 3 to \((3,3)\), East 1 to \((3,4)\) = 3 strokes.

Solution

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

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

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

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

    deque<tuple<int,int,int,int>> dq; // r, c, dir, remaining

    // Initialize: first stroke from source in each direction
    for (int d = 0; d < 4; d++) {
        int nr = sr + dr[d], nc = sc + dc[d];
        if (nr >= 0 && nr < H && nc >= 0 && nc < W
            && grid[nr][nc] == '.' && 1 < dist[nr][nc][d]) {
            dist[nr][nc][d] = 1;
            dq.push_back({nr, nc, d, K - 1});
        }
    }

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

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

        // Start new stroke in any direction: cost 1
        for (int nd = 0; nd < 4; nd++) {
            int nr = r + dr[nd], nc = c + dc[nd];
            if (nr >= 0 && nr < H && nc >= 0 && nc < W
                && grid[nr][nc] == '.'
                && cur + 1 < dist[nr][nc][nd]) {
                dist[nr][nc][nd] = cur + 1;
                dq.push_back({nr, nc, nd, K - 1});
            }
        }
    }

    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;
}

Why the Pruning Is Correct

Consider two paths reaching \((3,2)\) heading East:

  • Path A: 2 strokes, 1 remaining slide.
  • Path B: 2 strokes, 3 remaining slides.

Both have dist[3][2][E] = 2. Path B can slide further for free. If Path A is popped first, it extends one cell East. Then Path B is popped — but dist[3][2][E] is already 2, so it's not stale. It extends three cells East.

⚠ Gotcha. What if Path A is popped first and sets dist[3][3][E] = 2 via a new stroke (cost 1 from some other direction)? Then Path B arrives and slides to \((3,3)\) at cost 2 with push_front. It checks cur < dist[3][3][E] — \(2 < 2\) is false, so it skips. But that's fine: both paths reach \((3,3)\) at the same cost. No shortest path is missed.

The invariant: dist[r][c][d] records the minimum stroke count. Any entry popped from the deque with a higher value than dist[r][c][d] is stale and skipped. Cost-0 extensions are always processed before cost-1 extensions at the same stroke count (they're at the front). This guarantees correctness.

LC 1654 — Minimum Jumps to Reach Home

Problem. A bug on a number line at position 0. It wants to reach position \(x\). Each jump: forward \(a\) positions or backward \(b\) positions. It cannot jump backward twice in a row. Some positions are forbidden. Minimize jumps.

The direction twist. The "cannot jump backward twice in a row" constraint means the state needs a direction flag: (position, last_was_backward). Forward is always allowed. Backward is allowed only if the last jump was forward.

This isn't "continue free, turn costs 1" — every jump costs 1. But the direction constraint restricts which edges exist. The state expansion is the same idea: position alone isn't enough.

// State: (pos, last_backward)
// BFS since all edges cost 1
vector<vector<int>> dist(UB + 1, vector<int>(2, INT_MAX));
queue<pair<int,int>> q; // pos, last_backward
dist[0][0] = 0;
q.push({0, 0});

while (!q.empty()) {
    auto [pos, lb] = q.front(); q.pop();
    int d = dist[pos][lb];
    // Forward
    int nf = pos + a;
    if (nf <= UB && !forbidden[nf] && d + 1 < dist[nf][0]) {
        dist[nf][0] = d + 1;
        q.push({nf, 0});
    }
    // Backward (only if last wasn't backward)
    if (!lb) {
        int nb = pos - b;
        if (nb >= 0 && !forbidden[nb] && d + 1 < dist[nb][1]) {
            dist[nb][1] = d + 1;
            q.push({nb, 1});
        }
    }
}

⚠ Gotcha. The bug can overshoot \(x\) and come back. You need an upper bound on position to avoid infinite BFS. A safe bound is \(x + a + b\) (or \(\max(\text{max forbidden}, x) + a + b\)).

The General Pattern

Whenever a problem says:

  • "Choose a direction and move 1 to K steps"
  • "Each choice costs 1, sliding within a choice is free"
  • "Continuing straight is free, turning costs 1"

The recipe is:

  1. State = (position, direction, remaining_momentum).
  2. Continue = cost 0, push front.
  3. New direction = cost 1, push back.
  4. Distance table = dist[position][direction] (drop remaining).
  5. 0-1 BFS.

💡 Key insight. This is the same pattern as Lesson 2, but with a fuel gauge. Direction tells you where you're going. Remaining tells you how far you can still go for free. Both are state dimensions, but only direction appears in the distance table.

Exercises

  1. State space size. For Pond Skater with \(H = W = 1000\) and \(K = 1000\), what's the size of the distance table? What's the maximum deque size?

  2. K = 1 reduction. If \(K = 1\), the strider moves one cell per stroke. What does the problem reduce to? What's the optimal algorithm?

  3. Diagonal strider. Modify Pond Skater so the strider moves diagonally instead of cardinally. What changes in the code?

Problems

Problem Link Difficulty
AtCoder abc170_f — Pond Skater atcoder.jp/contests/abc170/tasks/abc170_f Hard
LC 1654 — Min Jumps to Reach Home leetcode.com/problems/minimum-jumps-to-reach-home Medium