Shortest Path in Binary Matrix
Real-world version: Fewest Tiles Across the FloorThe statement here is our own: the same inputs, outputs and technique.
A stockroom floor is an n x n grid of square tiles given as floor. floor[r][c] is 0 when the tile is free and 1 when a pallet stands on it, blocking the tile.
A picking robot has to get from the tile at the top-left corner to the tile at the bottom-right corner. From its current tile the robot can roll onto any of the up to eight tiles that touch it, including the four that only touch at a corner, as long as that tile is free. A route is the sequence of tiles the robot stands on, starting at the top-left tile and ending at the bottom-right tile, and every tile on it must be free.
Return the number of tiles on the shortest such route, counting both the tile it starts on and the tile it ends on. If no route exists, return -1.
Examples
Example 1
- Input
- floor = [[0, 0, 1], [1, 0, 1], [1, 0, 0]]
- Output
- 3
The robot rolls corner to corner through the middle tile: (0,0), then (1,1), then (2,2). Three tiles is the fewest possible on any board wider than one tile.
Example 2
- Input
- floor = [[0, 1, 1, 1], [0, 0, 1, 1], [1, 0, 0, 1], [1, 1, 0, 0]]
- Output
- 4
Pallets pen the robot into a staircase of free tiles, and the corner steps (0,0), (1,1), (2,2), (3,3) walk straight down it.
Example 3
- Input
- floor = [[0, 1, 0], [1, 1, 0], [0, 0, 0]]
- Output
- -1
All three tiles touching the starting corner carry pallets, so the robot cannot leave it and no route exists.
Constraints
- n == floor.length
- n == floor[i].length
- 1 <= n <= 100
- floor[i][j] is 0 or 1
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def fewest_tiles_across(floor: list[list[int]]) -> int:public int fewestTilesAcross(int[][] floor)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 16 test cases: 16 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's