How do you solve Castle on the Grid using the BFS with Slide Pruning (Optimal) approach?

When to use it: The refined version. Phrase it as 'same BFS, but cut a slide short once it reaches a cell already discovered at an earlier-or-equal level, since that cell already sweeps the rest of the line'. The correctness of BFS is untouched; the optimization removes redundant re-walking by reasoning about when a line is already fully covered. **The pruning rule.** Suppose we pop cell `u` at distance `d` and slide in some direction, reaching cell `v` with recorded distance `dv`: - If `v` is **unvisited** (`-1`): assign `d + 1`, enqueue, and continue the slide. - If `dv ≤ d`: `v` was discovered at an earlier-or-equal BFS level, so it has been or will be processed by the time level `d` finishes, and its own slide in this direction sweeps every cell beyond it — assigning them `dv + 1 ≤ d + 1`, which is no worse than what `u` would give. So the rest of the line is already optimal; **break**. - If `dv = d + 1`: `v` was reached this level from a *perpendicular* slide and has not yet swept this line. Beyond `v` there may be cells that only `u`'s slide reaches at `d + 1` (via `v` they'd cost `d + 2`). So **do not break** — keep walking, just don't reassign `v`. **Why the `dv = d + 1` distinction matters.** Naively breaking at the first visited cell is a classic bug: it can leave cells beyond a same-level cell to be reached one move too late, overestimating the answer. The safe rule breaks only when the encountered cell is from a strictly-or-equally-earlier layer. **Result.** Every line gets fully swept exactly once — by the earliest layer that enters it — collapsing the work to O(N²). The BFS layering still guarantees the first distance assigned to each cell (and to the goal) is the minimum number of moves. Time complexity: O(N²). Space complexity: O(N²).

Loading…

mediumGraphsFrequently asked

Castle on the Grid

Q: How do you solve Castle on the Grid using the Re-Expanding BFS (Baseline) approach?

When to use it: State the straightforward version first: BFS where each pop slides all four directions over their full open run, enqueuing newly reached cells but walking past already-visited ones to the wall. Recognizing the constant cost per slide reduces the problem to unweighted BFS; the implementation just needs the right neighbor rule. **Setup.** A `dist` matrix initialized to -1 (unvisited); set `dist[start] = 0` and enqueue the start. BFS pops cells in nondecreasing distance order. **Neighbor generation.** For a popped cell `(r, c)`, take each of the four direction vectors. Walk step by step: while the next cell is in bounds and not an `X`, it is reachable in one more move. If it's unvisited, set its distance to `dist[r][c] + 1` and enqueue it. Then keep stepping in the same direction until a wall or the border stops the slide. **Why it's correct.** Every slide is an edge of weight 1, and BFS settles all distance-`d` cells before any distance-`(d+1)` cell, so the first time a cell is assigned a distance, that distance is minimal. Returning `dist[goal]` (or detecting the goal on pop) yields the fewest moves. **Why we don't ship it as-is.** The baseline re-walks each line every time any cell on it is processed, because it strides past already-visited cells to the wall. That redundant scanning is the O(N³) cost the optimized version trims with a pruning rule. Time complexity: O(N³). Space complexity: O(N²).

Graphs · 29 of 34 · 12 min

You are given an N × N grid where each cell is . (open) or X (blocked), plus a start position (startRow, startCol) and a goal (goalRow, goalCol). A move picks one of the four directions (up, down, left, right) and slides the piece across consecutive open cells until it is stopped by the grid border or a blocked cell — you may stop at any open cell along that line, and the entire slide counts as one move.

Return the minimum number of moves to get from the start to the goal.

In plain English

The piece moves like a rook: in one move it travels in a straight line over any number of open cells until a wall or the border halts it. So the cost is the number of *slides*, not the number of cells crossed — a long straight glide is as cheap as a single step. That makes every slide an edge of weight 1, so the minimum number of moves is an unweighted shortest path, solvable by BFS. The only twist versus textbook grid BFS is neighbor generation: instead of the four adjacent cells, a cell's neighbors are *all* cells reachable along its four open runs.

Examples

Example 1

Input: grid = [".X.", ".X.", "..."], start = (0,0), goal = (0,2)
Output: 3
Note: Down from (0,0) to (2,0) [move 1], right to (2,2) [move 2], up to (0,2) [move 3]. The wall column blocks any shorter route.

Example 2

Input: grid = ["...", "...", "..."], start = (0,0), goal = (0,2)
Output: 1
Note: A single rightward slide from (0,0) glides across (0,1) to (0,2) — one move.

Example 3

Input: grid = ["..", ".."], start = (0,0), goal = (1,1)
Output: 2
Note: Right to (0,1) then down to (1,1), or down then right — either way two moves; no single slide reaches a diagonal.

Constraints

1 ≤ N ≤ 100 (square grid)
Each cell is '.' (open) or 'X' (blocked)
Start and goal are open cells; they may coincide (answer 0)
Coordinates are 0-indexed: (row, col), row downward, col rightward
A path from start to goal always exists for the given inputs

Clarifying questions4First question: Does a move cost the number of cells slid, or just one?Explore questions

Q1.Does a move cost the number of cells slid, or just one?
Just one. Sliding across five open cells is a single move, which is why this is unweighted BFS rather than Dijkstra.
Q2.Can I stop partway along a slide?
Yes — you may stop at any open cell on the line, so every cell along the run is reachable in that one move.
Q3.What stops a slide?
The grid border or a blocked 'X' cell. You can never enter or pass through an 'X'.
Q4.What if start equals goal?
Zero moves — the BFS returns the start's distance of 0 immediately.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A move slides the piece in one direction across any number of empty cells until a wall ('X') or the border stops it — every cell passed over in that slide is reachable in the same single move. Minimize moves with BFS where each pop expands all four directions over their full open run, assigning distance + 1 to newly reached cells. Stop the slide at a wall/edge, or prune it once it reaches a cell already discovered at an earlier-or-equal BFS level. O(N²) cells, near O(N²) with pruning.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model a 'slide until blocked' move as BFS over full-row/column neighbors (constant cost per slide), rather than weighting by distance, and handle walls, borders, and revisits correctly.

Where candidates slip

Adding the slide length to the cost (turning it into a weighted problem), stopping a slide at the first already-visited cell unconditionally (which can overestimate), or using DFS and losing the shortest-path guarantee.

How to stand out

Frame it as 'redefine neighbors as the whole open run, then it's vanilla unweighted BFS', and justify the pruning rule precisely — you may only stop a slide at a cell discovered at an earlier-or-equal level, never at a same-next-level cell.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Re-Expanding BFS (Baseline)	`O(N³)`	`O(N²)`	State the straightforward version first: BFS where each pop slides all four directions over their full open run, enqueuing newly reached cells but walking past already-visited ones to the wall.	Read
2	BFS with Slide Pruning (Optimal)Optimal	`O(N²)`	`O(N²)`	The refined version. Phrase it as 'same BFS, but cut a slide short once it reaches a cell already discovered at an earlier-or-equal level, since that cell already sweeps the rest of the line'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMin moves on a gridCost per move?= cells crossed= 1 per slideExplore the full tree

The sample grid and the 3-move path

How to read it:The middle column of 'X' forces a detour: down, right, up.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Re-Expanding BFS (Baseline)

TimeO(N³)SpaceO(N²)

State the straightforward version first: BFS where each pop slides all four directions over their full open run, enqueuing newly reached cells but walking past already-visited ones to the wall.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each move costs 1 regardless of slide length, so this is an unweighted shortest path — what algorithm gives minimum unweighted distance?

2Hint 2Explore hint

BFS. The only change from textbook grid BFS is the neighbor rule: from a cell, slide in each of the four directions and treat every open cell on the run as a neighbor at distance + 1.

3Hint 3Explore hint

Walk each direction to the wall/border, assigning distance to unvisited cells. Continuing past visited cells re-walks lines, but it's simple and correct — O(N³).

A · Core idea

Recognizing the constant cost per slide reduces the problem to unweighted BFS; the implementation just needs the right neighbor rule.

Setup. A dist matrix initialized to -1 (unvisited); set dist[start] = 0 and enqueue the start. BFS pops cells in nondecreasing distance order.

Neighbor generation. For a popped cell (r, c), take each of the four direction vectors. Walk step by step: while the next cell is in bounds and not an X, it is reachable in one more move. If it's unvisited, set its distance to dist[r][c] + 1 and enqueue it. Then keep stepping in the same direction until a wall or the border stops the slide.

Why it's correct. Every slide is an edge of weight 1, and BFS settles all distance-d cells before any distance-(d+1) cell, so the first time a cell is assigned a distance, that distance is minimal. Returning dist[goal] (or detecting the goal on pop) yields the fewest moves.

Why we don't ship it as-is. The baseline re-walks each line every time any cell on it is processed, because it strides past already-visited cells to the wall. That redundant scanning is the O(N³) cost the optimized version trims with a pruning rule.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

grid = [".X.", ".X.", "..."], start = (0,0), goal = (0,2)

Array state

init

start at (0,0)

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

Reference implementation previewpublic int minimumMoves(String[] grid, int startRow, int startCol, int goalRow, int goalCol) { int n = grid.length; int[][] dist = new int[n][n]; for (int[] row : dist) Arrays.fill(row, -1); int[] dr = {-1, 1, 0, 0};Explore the full code

solution.javaJava

Re-Expanding BFS (Baseline) — reference

3 teaching notes

1
public int minimumMoves(String[] grid, int startRow, int startCol, int goalRow, int goalCol) {
2
    int n = grid.length;
3
    int[][] dist = new int[n][n];
4
    for (int[] row : dist) Arrays.fill(row, -1);
5
    int[] dr = {-1, 1, 0, 0};
6
    int[] dc = {0, 0, -1, 1};
7
    Deque<int[]> queue = new ArrayDeque<>();
8
    dist[startRow][startCol] = 0;
9
    queue.offer(new int[]{startRow, startCol});
10
    while (!queue.isEmpty()) {
11
        int[] cur = queue.poll();
12
        int r = cur[0], c = cur[1];
13
        if (r == goalRow && c == goalCol) return dist[r][c];
14
        for (int d = 0; d < 4; d++) {
15
            int nr = r + dr[d], nc = c + dc[d];
16
            // Slide continues while in bounds and not blocked — the border or an X ends
17
            // the run.
18
            while (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr].charAt(nc) != 'X') {
19
                if (dist[nr][nc] == -1) {
20
                    // Every cell on the slide is one move from the current cell,
21
                    // regardless of how far along it is.
22
                    dist[nr][nc] = dist[r][c] + 1;
23
                    queue.offer(new int[]{nr, nc});
24
                }
25
                // The baseline strides on even past visited cells, re-walking lines —
26
                // the O(N³) cost.
27
                nr += dr[d];          // baseline: keep walking past visited cells
28
                nc += dc[d];
29
            }
30
        }
31
    }
32
    return dist[goalRow][goalCol];
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(N³) timeO(N²) spaceOpen the invariant and proofExplore the proof

The whole problem is 'unweighted BFS with a custom neighbor function'. Once neighbors are defined as 'every cell in the open run', no special distance math is needed — the count of BFS layers is the answer.

ComplexityO(N³) time, O(N²) space — There are N² cells; each is dequeued once. From each, the four slides can traverse up to N cells, and the baseline keeps walking even past already-visited cells, so a single pop costs O(N). Total O(N² · N) = O(N³). With N ≤ 100 that's ~10⁶ — fast enough, but it re-scans the same lines repeatedly.

E · Edge cases and pitfalls3Adding slide length to the cost — turns an unweighted problem into a weighted one with wrong answers.Explore edge cases

Pitfalls

Adding slide length to the cost — turns an unweighted problem into a weighted one with wrong answers.
Using DFS instead of BFS — loses the shortest-path guarantee.
Forgetting to stop the slide at an 'X' or the border.

03.2

Approach 2 of 2 · Optimal

BFS with Slide Pruning (Optimal)

TimeO(N²)SpaceO(N²)

The refined version. Phrase it as 'same BFS, but cut a slide short once it reaches a cell already discovered at an earlier-or-equal level, since that cell already sweeps the rest of the line'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The baseline re-walks each line many times. When sliding and you reach a cell already reached at distance ≤ the current cell's distance, what does that tell you about the cells beyond it?

2Hint 2Explore hint

That cell was (or will be) processed no later than now, and when processed it sweeps the same line — so the cells beyond it are already covered optimally. You can stop the slide there.

3Hint 3Explore hint

But do NOT stop at a cell whose distance equals current + 1: it was reached from a perpendicular direction and may not have swept this line yet, so keep walking past it.

A · Core idea

The correctness of BFS is untouched; the optimization removes redundant re-walking by reasoning about when a line is already fully covered.

The pruning rule. Suppose we pop cell u at distance d and slide in some direction, reaching cell v with recorded distance dv:

If v is unvisited (-1): assign d + 1, enqueue, and continue the slide.
If dv ≤ d: v was discovered at an earlier-or-equal BFS level, so it has been or will be processed by the time level d finishes, and its own slide in this direction sweeps every cell beyond it — assigning them dv + 1 ≤ d + 1, which is no worse than what u would give. So the rest of the line is already optimal; break.
If dv = d + 1: v was reached this level from a perpendicular slide and has not yet swept this line. Beyond v there may be cells that only u's slide reaches at d + 1 (via v they'd cost d + 2). So do not break — keep walking, just don't reassign v.

Why the `dv = d + 1` distinction matters. Naively breaking at the first visited cell is a classic bug: it can leave cells beyond a same-level cell to be reached one move too late, overestimating the answer. The safe rule breaks only when the encountered cell is from a strictly-or-equally-earlier layer.

Result. Every line gets fully swept exactly once — by the earliest layer that enters it — collapsing the work to O(N²). The BFS layering still guarantees the first distance assigned to each cell (and to the goal) is the minimum number of moves.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

grid = [".X.", ".X.", "..."], start = (0,0), goal = (0,2)

Array state

row 0

(0,0)=0, (0,1)=X, (0,2)=3

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

BFS with Slide Pruning (Optimal) — optimal

3 teaching notes

1
public int minimumMoves(String[] grid, int startRow, int startCol, int goalRow, int goalCol) {
2
    int n = grid.length;
3
    int[][] dist = new int[n][n];
4
    for (int[] row : dist) Arrays.fill(row, -1);
5
    int[] dr = {-1, 1, 0, 0};
6
    int[] dc = {0, 0, -1, 1};
7
    Deque<int[]> queue = new ArrayDeque<>();
8
    dist[startRow][startCol] = 0;
9
    queue.offer(new int[]{startRow, startCol});
10
    while (!queue.isEmpty()) {
11
        int[] cur = queue.poll();
12
        int r = cur[0], c = cur[1];
13
        if (r == goalRow && c == goalCol) return dist[r][c];
14
        int d = dist[r][c];
15
        for (int dir = 0; dir < 4; dir++) {
16
            int nr = r + dr[dir], nc = c + dc[dir];
17
            while (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr].charAt(nc) != 'X') {
18
                // Unvisited cell on the slide → reachable now in d + 1 moves.
19
                if (dist[nr][nc] == -1) {
20
                    dist[nr][nc] = d + 1;
21
                    queue.offer(new int[]{nr, nc});
22
                } else if (dist[nr][nc] <= d) {
23
                    break;            // earlier/equal level already sweeps the rest
24
                }
25
                // A same-next-level cell was reached perpendicularly; cells beyond it
26
                // may still need this slide, so continue.
27
                // dist == d + 1: keep walking, do not reassign
28
                nr += dr[dir];
29
                nc += dc[dir];
30
            }
31
        }
32
    }
33
    return dist[goalRow][goalCol];
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(N²) timeO(N²) spaceOpen the invariant and proofExplore the proof

The subtlety isn't the BFS — it's knowing exactly when a slide is redundant. A cell already reached at an earlier-or-equal level dominates the rest of its line; a same-next-level cell does not. Encoding that precisely turns an O(N³) re-scan into an O(N²) sweep without sacrificing correctness.

ComplexityO(N²) time, O(N²) space — With the pruning rule, each grid line is fully swept only by the earliest BFS level that touches it; later slides into it stop immediately. Each of the N² cells is assigned once, and the total sweeping work amortizes to O(N²). Space is the O(N²) distance grid and queue.

E · Edge cases and pitfalls7start == goal — The start is popped first; the goal check returns dist = 0 with no moves.Explore edge cases

Edge cases handled

start == goalThe start is popped first; the goal check returns dist = 0 with no moves.
goal reachable in one straight slideThe start's slide assigns the goal distance 1, returned when the goal is later popped.
Walls splitting the grid into a mazeBFS layers route around 'X' cells; the answer counts each direction change as one move.

Pitfalls

Breaking the slide at the first visited cell unconditionally — overestimates when that cell is at distance d + 1.
Treating slide length as cost — use Dijkstra only if the problem actually weights by distance.
Off-by-one in bounds or reading grid[nr][nc] before the bounds check.
Returning before the goal is dequeued when distances on enqueue would also work — both are fine, but be consistent.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int minimumMoves(String[] grid, int startRow, int startCol, int goalRow, int goalCol) { int n = grid.length; int[][] dist = new int[n][n]; for (int[] row : dist) Arrays.fill(row, -1); int[] dr = {-1, 1, 0, 0};Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public int minimumMoves(String[] grid, int startRow, int startCol, int goalRow, int goalCol) {
    int n = grid.length;
    int[][] dist = new int[n][n];
    for (int[] row : dist) Arrays.fill(row, -1);
    int[] dr = {-1, 1, 0, 0};
    int[] dc = {0, 0, -1, 1};
    Deque<int[]> queue = new ArrayDeque<>();
    dist[startRow][startCol] = 0;
    queue.offer(new int[]{startRow, startCol});
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        int r = cur[0], c = cur[1];
        if (r == goalRow && c == goalCol) return dist[r][c];
        int d = dist[r][c];
        for (int dir = 0; dir < 4; dir++) {
            int nr = r + dr[dir], nc = c + dc[dir];
            while (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr].charAt(nc) != 'X') {
                if (dist[nr][nc] == -1) {
                    dist[nr][nc] = d + 1;
                    queue.offer(new int[]{nr, nc});
                } else if (dist[nr][nc] <= d) {
                    break;            // earlier/equal level already sweeps the rest
                }
                // dist == d + 1: keep walking, do not reassign
                nr += dr[dir];
                nc += dc[dir];
            }
        }
    }
    return dist[goalRow][goalCol];
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Weighting by slide length

Each slide is one move no matter how far it travels. Adding the number of cells crossed makes it a weighted problem and yields the wrong minimum.

Explore the code comparison

Don't write this

dist[nr][nc] = dist[r][c] + steps   # steps = cells slid — wrong cost model

Write this instead

dist[nr][nc] = dist[r][c] + 1       # one move per slide

Unconditional break on visited

Breaking at the first already-visited cell is unsafe when that cell sits at distance d + 1 (reached perpendicularly): cells beyond it may only be reachable at d + 1 through this slide, so stopping records them as d + 2.

Explore the code comparison

Don't write this

if (dist[nr][nc] != -1) break;   // breaks even on same-next-level cells

Write this instead

if (dist[nr][nc] == -1) { dist[nr][nc] = d + 1; queue.offer(...); }
else if (dist[nr][nc] <= d) break;   // only earlier/equal levels

DFS instead of BFS

Move minimization is an unweighted shortest path; DFS explores deeply and can settle a cell with a non-minimal move count, returning a wrong answer.

Explore the code comparison

Don't write this

stack = [(start_row, start_col)]   # LIFO → depth-first, not shortest

Write this instead

queue = deque([(start_row, start_col)])   # FIFO → BFS, shortest first

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

BFS where each move expands a full row/column run

Code pattern to memorize

dist[start] = 0, queue = [start]
while queue:
    (r, c) = pop
    if (r, c) == goal: return dist[r][c]
    for each of 4 directions (dr, dc):
        nr, nc = r+dr, c+dc
        while in-bounds and grid[nr][nc] != 'X':
            if dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                enqueue (nr, nc)
            elif dist[nr][nc] <= dist[r][c]:
                break        # already swept by an earlier/equal level
            nr += dr; nc += dc

Rules to remember

1One move = a full slide: every empty cell between the start and the stopping wall/edge costs the same single move.
2BFS (not DFS) gives the minimum because all cells at distance d are settled before any at d + 1.
3Keep walking past same-level cells (distance == d + 1): they were reached via a different direction and may not have swept this line yet.
4Prune a slide only when it hits a cell with distance ≤ current d — that cell already sweeps the rest of the line.
5Stop a slide at the border or an 'X'; the cell holding the 'X' is not enterable.

Use this pattern when

Shortest path on a grid where a 'move' covers a **variable distance** in a straight line
Unweighted in the sense that every slide costs exactly 1 → BFS
Rook/queen/laser-style motion: slide until blocked
You need the minimum number of moves, not the exact cells traversed

Choose another pattern when

Each step costs the cell-to-cell distance (weighted) → Dijkstra/0-1 BFS, not plain BFS
Moves are single-cell only → standard 4-neighbor grid BFS
Diagonal or knight moves → different neighbor generation
You must output the path of cells → store parent pointers, not just distances

Interview takeaway

Castle on the Grid is BFS with a non-standard neighbor rule: a node's neighbors are *all* cells reachable in one straight slide, not just the four adjacent cells. Once you redefine 'neighbor' as 'every cell in the open run', the classic unweighted-shortest-path BFS solves it unchanged.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical Unweighted BFS with a Custom Neighbor Rule. Recognize it when a single 'move' covers a variable straight-line distance: redefine a cell's neighbors as every cell in its open run, then run plain BFS. The pruning insight — stop a slide only at cells discovered at an earlier-or-equal level — drops the re-scan from O(N³) to O(N²) without affecting correctness.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Snakes and Ladders: The Quickest Way Up
BFS on a board where each move jumps to up to six cells (plus snakes/ladders) — same constant-cost-per-move idea.
Minimum Knight Moves
Coming soon
BFS with knight-shaped neighbor generation; still one move per jump.
Jump Game / Reachable in Slides
Coming soon
1-D analog: each position reaches a range in one move — BFS by layers of moves.
Shortest Path in a Grid with Obstacles
Coming soon
Standard 4-neighbor grid BFS when each move is a single cell, not a slide.

Same pattern

←

Snakes and Ladders: The Quickest Way Up

Continue · Next problem

Floyd: City of Blinding Lights

mediumGraphsFrequently asked

Castle on the Grid

Graphs · 29 of 34 · 12 min

Return the minimum number of moves to get from the start to the goal.

In plain English

Examples

Example 1

Input: grid = [".X.", ".X.", "..."], start = (0,0), goal = (0,2)
Output: 3
Note: Down from (0,0) to (2,0) [move 1], right to (2,2) [move 2], up to (0,2) [move 3]. The wall column blocks any shorter route.

Example 2

Input: grid = ["...", "...", "..."], start = (0,0), goal = (0,2)
Output: 1
Note: A single rightward slide from (0,0) glides across (0,1) to (0,2) — one move.

Example 3

Input: grid = ["..", ".."], start = (0,0), goal = (1,1)
Output: 2
Note: Right to (0,1) then down to (1,1), or down then right — either way two moves; no single slide reaches a diagonal.

Constraints

1 ≤ N ≤ 100 (square grid)
Each cell is '.' (open) or 'X' (blocked)
Start and goal are open cells; they may coincide (answer 0)
Coordinates are 0-indexed: (row, col), row downward, col rightward
A path from start to goal always exists for the given inputs

Clarifying questions4First question: Does a move cost the number of cells slid, or just one?Explore questions

Q1.Does a move cost the number of cells slid, or just one?
Just one. Sliding across five open cells is a single move, which is why this is unweighted BFS rather than Dijkstra.
Q2.Can I stop partway along a slide?
Yes — you may stop at any open cell on the line, so every cell along the run is reachable in that one move.
Q3.What stops a slide?
The grid border or a blocked 'X' cell. You can never enter or pass through an 'X'.
Q4.What if start equals goal?
Zero moves — the BFS returns the start's distance of 0 immediately.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model a 'slide until blocked' move as BFS over full-row/column neighbors (constant cost per slide), rather than weighting by distance, and handle walls, borders, and revisits correctly.

Where candidates slip

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Re-Expanding BFS (Baseline)	`O(N³)`	`O(N²)`	State the straightforward version first: BFS where each pop slides all four directions over their full open run, enqueuing newly reached cells but walking past already-visited ones to the wall.	Read
2	BFS with Slide Pruning (Optimal)Optimal	`O(N²)`	`O(N²)`	The refined version. Phrase it as 'same BFS, but cut a slide short once it reaches a cell already discovered at an earlier-or-equal level, since that cell already sweeps the rest of the line'.	Read

The sample grid and the 3-move path

How to read it:The middle column of 'X' forces a detour: down, right, up.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Re-Expanding BFS (Baseline)

TimeO(N³)SpaceO(N²)

State the straightforward version first: BFS where each pop slides all four directions over their full open run, enqueuing newly reached cells but walking past already-visited ones to the wall.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each move costs 1 regardless of slide length, so this is an unweighted shortest path — what algorithm gives minimum unweighted distance?

2Hint 2Explore hint

BFS. The only change from textbook grid BFS is the neighbor rule: from a cell, slide in each of the four directions and treat every open cell on the run as a neighbor at distance + 1.

3Hint 3Explore hint

Walk each direction to the wall/border, assigning distance to unvisited cells. Continuing past visited cells re-walks lines, but it's simple and correct — O(N³).

A · Core idea

Recognizing the constant cost per slide reduces the problem to unweighted BFS; the implementation just needs the right neighbor rule.

Setup. A dist matrix initialized to -1 (unvisited); set dist[start] = 0 and enqueue the start. BFS pops cells in nondecreasing distance order.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

grid = [".X.", ".X.", "..."], start = (0,0), goal = (0,2)

Array state

init

start at (0,0)

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Re-Expanding BFS (Baseline) — reference

3 teaching notes

1
public int minimumMoves(String[] grid, int startRow, int startCol, int goalRow, int goalCol) {
2
    int n = grid.length;
3
    int[][] dist = new int[n][n];
4
    for (int[] row : dist) Arrays.fill(row, -1);
5
    int[] dr = {-1, 1, 0, 0};
6
    int[] dc = {0, 0, -1, 1};
7
    Deque<int[]> queue = new ArrayDeque<>();
8
    dist[startRow][startCol] = 0;
9
    queue.offer(new int[]{startRow, startCol});
10
    while (!queue.isEmpty()) {
11
        int[] cur = queue.poll();
12
        int r = cur[0], c = cur[1];
13
        if (r == goalRow && c == goalCol) return dist[r][c];
14
        for (int d = 0; d < 4; d++) {
15
            int nr = r + dr[d], nc = c + dc[d];
16
            // Slide continues while in bounds and not blocked — the border or an X ends
17
            // the run.
18
            while (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr].charAt(nc) != 'X') {
19
                if (dist[nr][nc] == -1) {
20
                    // Every cell on the slide is one move from the current cell,
21
                    // regardless of how far along it is.
22
                    dist[nr][nc] = dist[r][c] + 1;
23
                    queue.offer(new int[]{nr, nc});
24
                }
25
                // The baseline strides on even past visited cells, re-walking lines —
26
                // the O(N³) cost.
27
                nr += dr[d];          // baseline: keep walking past visited cells
28
                nc += dc[d];
29
            }
30
        }
31
    }
32
    return dist[goalRow][goalCol];
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(N³) timeO(N²) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Adding slide length to the cost — turns an unweighted problem into a weighted one with wrong answers.Explore edge cases

Pitfalls

Adding slide length to the cost — turns an unweighted problem into a weighted one with wrong answers.
Using DFS instead of BFS — loses the shortest-path guarantee.
Forgetting to stop the slide at an 'X' or the border.

03.2

Approach 2 of 2 · Optimal

BFS with Slide Pruning (Optimal)

TimeO(N²)SpaceO(N²)

The refined version. Phrase it as 'same BFS, but cut a slide short once it reaches a cell already discovered at an earlier-or-equal level, since that cell already sweeps the rest of the line'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The baseline re-walks each line many times. When sliding and you reach a cell already reached at distance ≤ the current cell's distance, what does that tell you about the cells beyond it?

2Hint 2Explore hint

That cell was (or will be) processed no later than now, and when processed it sweeps the same line — so the cells beyond it are already covered optimally. You can stop the slide there.

3Hint 3Explore hint

But do NOT stop at a cell whose distance equals current + 1: it was reached from a perpendicular direction and may not have swept this line yet, so keep walking past it.

A · Core idea

The correctness of BFS is untouched; the optimization removes redundant re-walking by reasoning about when a line is already fully covered.

The pruning rule. Suppose we pop cell u at distance d and slide in some direction, reaching cell v with recorded distance dv:

If v is unvisited (-1): assign d + 1, enqueue, and continue the slide.
If dv ≤ d: v was discovered at an earlier-or-equal BFS level, so it has been or will be processed by the time level d finishes, and its own slide in this direction sweeps every cell beyond it — assigning them dv + 1 ≤ d + 1, which is no worse than what u would give. So the rest of the line is already optimal; break.
If dv = d + 1: v was reached this level from a perpendicular slide and has not yet swept this line. Beyond v there may be cells that only u's slide reaches at d + 1 (via v they'd cost d + 2). So do not break — keep walking, just don't reassign v.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

grid = [".X.", ".X.", "..."], start = (0,0), goal = (0,2)

Array state

row 0

(0,0)=0, (0,1)=X, (0,2)=3

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

BFS with Slide Pruning (Optimal) — optimal

3 teaching notes

1
public int minimumMoves(String[] grid, int startRow, int startCol, int goalRow, int goalCol) {
2
    int n = grid.length;
3
    int[][] dist = new int[n][n];
4
    for (int[] row : dist) Arrays.fill(row, -1);
5
    int[] dr = {-1, 1, 0, 0};
6
    int[] dc = {0, 0, -1, 1};
7
    Deque<int[]> queue = new ArrayDeque<>();
8
    dist[startRow][startCol] = 0;
9
    queue.offer(new int[]{startRow, startCol});
10
    while (!queue.isEmpty()) {
11
        int[] cur = queue.poll();
12
        int r = cur[0], c = cur[1];
13
        if (r == goalRow && c == goalCol) return dist[r][c];
14
        int d = dist[r][c];
15
        for (int dir = 0; dir < 4; dir++) {
16
            int nr = r + dr[dir], nc = c + dc[dir];
17
            while (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr].charAt(nc) != 'X') {
18
                // Unvisited cell on the slide → reachable now in d + 1 moves.
19
                if (dist[nr][nc] == -1) {
20
                    dist[nr][nc] = d + 1;
21
                    queue.offer(new int[]{nr, nc});
22
                } else if (dist[nr][nc] <= d) {
23
                    break;            // earlier/equal level already sweeps the rest
24
                }
25
                // A same-next-level cell was reached perpendicularly; cells beyond it
26
                // may still need this slide, so continue.
27
                // dist == d + 1: keep walking, do not reassign
28
                nr += dr[dir];
29
                nc += dc[dir];
30
            }
31
        }
32
    }
33
    return dist[goalRow][goalCol];
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(N²) timeO(N²) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7start == goal — The start is popped first; the goal check returns dist = 0 with no moves.Explore edge cases

Edge cases handled

start == goalThe start is popped first; the goal check returns dist = 0 with no moves.
goal reachable in one straight slideThe start's slide assigns the goal distance 1, returned when the goal is later popped.
Walls splitting the grid into a mazeBFS layers route around 'X' cells; the answer counts each direction change as one move.

Pitfalls

Breaking the slide at the first visited cell unconditionally — overestimates when that cell is at distance d + 1.
Treating slide length as cost — use Dijkstra only if the problem actually weights by distance.
Off-by-one in bounds or reading grid[nr][nc] before the bounds check.
Returning before the goal is dequeued when distances on enqueue would also work — both are fine, but be consistent.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Weighting by slide length

Each slide is one move no matter how far it travels. Adding the number of cells crossed makes it a weighted problem and yields the wrong minimum.

Explore the code comparison

Don't write this

dist[nr][nc] = dist[r][c] + steps   # steps = cells slid — wrong cost model

Write this instead

dist[nr][nc] = dist[r][c] + 1       # one move per slide

Unconditional break on visited

Explore the code comparison

Don't write this

if (dist[nr][nc] != -1) break;   // breaks even on same-next-level cells

Write this instead

if (dist[nr][nc] == -1) { dist[nr][nc] = d + 1; queue.offer(...); }
else if (dist[nr][nc] <= d) break;   // only earlier/equal levels

DFS instead of BFS

Move minimization is an unweighted shortest path; DFS explores deeply and can settle a cell with a non-minimal move count, returning a wrong answer.

Explore the code comparison

Don't write this

stack = [(start_row, start_col)]   # LIFO → depth-first, not shortest

Write this instead

queue = deque([(start_row, start_col)])   # FIFO → BFS, shortest first

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

BFS where each move expands a full row/column run

Code pattern to memorize

dist[start] = 0, queue = [start]
while queue:
    (r, c) = pop
    if (r, c) == goal: return dist[r][c]
    for each of 4 directions (dr, dc):
        nr, nc = r+dr, c+dc
        while in-bounds and grid[nr][nc] != 'X':
            if dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                enqueue (nr, nc)
            elif dist[nr][nc] <= dist[r][c]:
                break        # already swept by an earlier/equal level
            nr += dr; nc += dc

Rules to remember

1One move = a full slide: every empty cell between the start and the stopping wall/edge costs the same single move.
2BFS (not DFS) gives the minimum because all cells at distance d are settled before any at d + 1.
3Keep walking past same-level cells (distance == d + 1): they were reached via a different direction and may not have swept this line yet.
4Prune a slide only when it hits a cell with distance ≤ current d — that cell already sweeps the rest of the line.
5Stop a slide at the border or an 'X'; the cell holding the 'X' is not enterable.

Use this pattern when

Shortest path on a grid where a 'move' covers a **variable distance** in a straight line
Unweighted in the sense that every slide costs exactly 1 → BFS
Rook/queen/laser-style motion: slide until blocked
You need the minimum number of moves, not the exact cells traversed

Choose another pattern when

Each step costs the cell-to-cell distance (weighted) → Dijkstra/0-1 BFS, not plain BFS
Moves are single-cell only → standard 4-neighbor grid BFS
Diagonal or knight moves → different neighbor generation
You must output the path of cells → store parent pointers, not just distances

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Snakes and Ladders: The Quickest Way Up
BFS on a board where each move jumps to up to six cells (plus snakes/ladders) — same constant-cost-per-move idea.
Minimum Knight Moves
Coming soon
BFS with knight-shaped neighbor generation; still one move per jump.
Jump Game / Reachable in Slides
Coming soon
1-D analog: each position reaches a range in one move — BFS by layers of moves.
Shortest Path in a Grid with Obstacles
Coming soon
Standard 4-neighbor grid BFS when each move is a single cell, not a slide.

Same pattern

←

Snakes and Ladders: The Quickest Way Up

Continue · Next problem

Floyd: City of Blinding Lights