Shortest path on a grid — rat in a maze, knight moves, snake & ladder

Medium

Problem

Unweighted shortest-path problems, all solved with BFS:

Knight moves — the minimum number of knight moves from a source square to a target square on an n × n board. Snake & ladder — the minimum number of dice throws to go from square 1 to the last square, following snakes and ladders. Maze — the fewest steps from the start to the exit, moving through open cells only.

Example 1

Input:  knight: n = 6, from (4,5) to (1,1)
Output: 3

Also asked as: Search in a Maze · Minimum Step by Knight · Snake and Ladders Problem · Rat in a maze Problem

Test cases

Case 1

Input:    6, [4,5], [1,1]
Expected: 3

Case 2

Input:    8, [0,0], [1,2]
Expected: 1

Case 3

Input:    8, [0,0], [7,7]
Expected: 6

Case 4

Input:    8, [3,3], [3,3]
Expected: 0

Case 5

Input:    2, [0,0], [1,1]
Expected: -1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. BFS (unweighted shortest path)

Time O(cells)Space O(cells)

Every cell/state is a node; edges are legal moves. BFS from the start gives the minimum number of moves. Snake & ladder: nodes are board squares 1..100, edges are dice rolls, jumps rewrite the destination.

function minKnightMoves(N, start, target) {
const moves = [[1,2],[2,1],[-1,2],[-2,1],[1,-2],[2,-1],[-1,-2],[-2,-1]];
const seen = Array.from({ length: N }, () => Array(N).fill(false));
let q = [[...start, 0]];
seen[start[0]][start[1]] = true;
while (q.length) {
const next = [];
for (const [r, c, d] of q) {
if (r === target[0] && c === target[1]) return d;
for (const [dr, dc] of moves) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nc >= 0 && nr < N && nc < N && !seen[nr][nc]) { seen[nr][nc] = true; next.push([nr, nc, d + 1]); }
}
}
q = next;
}
return -1;
}

Rat in a maze wants ALL paths, not the shortest — that is backtracking (record the path, mark/unmark visited cells).