Shortest path on a grid — rat in a maze, knight moves, snake & ladder
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
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).