Medium · Matrices

Find path between cells

Given an m × n grid of 0s (open) and 1s (walls), a start cell (sx, sy) and a destination cell (dx, dy) given as (row, column), return any path of 4-adjacent open cells from the start to the destination as a list of [row, column] pairs including both ends, or null if no such path exists.

Examples

Example 1

{
  "mat": [
    [0, 0, 1, 0],
    [1, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 1, 1, 0]
  ],
  "sx": 0,
  "sy": 0,
  "dx": 3,
  "dy": 3
}

Output: [[0,0],[0,1],[1,1],[2,1],[2,2],[2,3],[3,3]]

Example 2

{
  "mat": [
    [0, 1, 0],
    [1, 1, 0],
    [0, 0, 0]
  ],
  "sx": 0,
  "sy": 0,
  "dx": 2,
  "dy": 0
}

Output: null (no path)

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.