Solve grid shortest path and robot cleaning

Question

LeetCode 1091. Shortest Path in Binary Matrix; LeetCode 489. Robot Room Cleaner

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ https://leetcode.com/problems/robot-room-cleaner/description/

Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1). If there is no clear path, return -1.

A clear path is a path from (0, 0) to (n-1, n-1) such that:

• All visited cells of the path are 0 (open).
• All adjacent cells of the path are connected 8-directionally (they share an edge or a corner).

The length of a clear path is the number of visited cells along that path (counting both the start and end cell).

Return -1 if the start or end cell is blocked, or if no clear path exists.

Example: grid = [[0,1],[1,0]] -> 2 (path: (0,0) -> (1,1)). Example: grid = [[0,0,0],[1,1,0],[1,1,0]] -> 4. Example: grid = [[1,0,0],[1,1,0],[1,1,0]] -> -1 (start is blocked).

This is LeetCode 1091.

Constraints

• n == grid.length == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1

Hints

1. Each cell has 8 neighbors (including diagonals). BFS explores cells in order of distance, so the first time you reach (n-1, n-1) gives the shortest path length.
2. Count cells, not edges: start the BFS distance at 1 for the start cell.
3. Guard the trivial blockers first: if grid[0][0] or grid[n-1][n-1] is 1, immediately return -1.

Robot Room Cleaner (Count Cleaned Cells)

A robot starts on an open cell of an m x n grid and must clean every open cell it can reach. In the original problem the robot only senses the room through a movement API; here we model it as an executable challenge over a known grid.

You are given:

• grid: an m x n matrix where 1 means an open cell and 0 means an obstacle/wall.
• start_row, start_col: the robot's starting position (guaranteed to be inside the grid).

The robot can move to any of the 4 edge-adjacent cells (up, right, down, left). It cleans a cell when it first stands on it and can only pass through open (1) cells. Using DFS with backtracking, the robot will clean every open cell reachable from its start.

Return the number of distinct cells the robot cleans. If the starting cell is itself an obstacle, return 0.

Example: grid = [[1,1,1],[1,1,1],[1,1,1]], start (1, 1) -> 9 (the whole room is reachable).

This is the executable form of LeetCode 489.

Constraints

• 1 <= m, n <= 100
• grid[i][j] is 0 (obstacle) or 1 (open)
• 0 <= start_row < m, 0 <= start_col < n

Hints

1. Treat the reachable open cells as a connected component: a DFS/flood-fill from the start over 4-directional moves through open cells visits exactly the cells the robot can clean.
2. Track cleaned cells in a visited set so you never re-clean or loop. The count is the size of that set.
3. The real LeetCode 489 forces backtracking because the robot has no coordinates; here you have the grid, so a plain DFS that returns after exploring each branch already mirrors the backtracking behavior.