Compute reachable cells for a cleaning robot

You are given a 2D grid representing a floor plan:

• 0 = free cell (the robot may stand on it)
• 1 = blocked cell (obstacle)

The robot can move from a cell to any of its 8 neighbors (up, down, left, right, and 4 diagonals) as long as the destination cell is allowed under the rules of the sub-question.

Return answers as a set/list of reachable coordinates (r, c) (order does not matter).

Sub-question 1 (basic reachability)

Input: grid m x n and a start cell (sr, sc) that is free.

Task: return all free cells reachable from (sr, sc) using 8-direction moves.

Sub-question 2 (one obstacle can be cleared)

Same as Sub-question 1, except the robot may convert at most one blocked cell (1) into free (0) during its traversal (think: it can clear/remove one obstacle exactly once).

Task: return all cells that are reachable under this rule.

Sub-question 3 (two robots)

Input: grid m x n and two start cells (s1r, s1c) and (s2r, s2c) that are free.

Task: return the set of cells that are reachable by at least one of the two robots (union of their reachable areas) using 8-direction moves.

Constraints (assume)

• 1 <= m, n <= 2000 (choose an approach that is safe for large grids)
• Grid is not necessarily fully connected.
• Start cells are within bounds.

Clarify in the interview how to represent the returned set for large outputs (e.g., boolean mask vs coordinate list).