Find nearest room; extend to two users

You are given an m×n grid where 1 is a wall (impassable), 0 is an empty cell, and 2 is a meeting room. From a starting coordinate [r, c], you may move up, down, left, or right with cost 1 per step. Return the coordinates of the closest meeting room reachable from the start; if none are reachable, return [-1, -1]. Use the example grid [[0,0,1,0],[0,2,1,0],[0,2,1,0]] with start [0,0] where the expected output is [1,1]. Discuss your algorithm and time/space complexity. Follow-up: given two starting users s1 and s2, return the meeting room that minimizes the sum of their shortest-path distances (consider only rooms reachable by both) and also return that minimum total distance. Explain your approach and complexity.

Nearest Meeting Room (BFS)

You are given an m x n grid where 1 is a wall (impassable), 0 is an empty cell, and 2 is a meeting room. Starting from coordinate [r, c], you may move up, down, left, or right with cost 1 per step (you cannot step onto walls). Return the coordinates [row, col] of the closest meeting room reachable from the start. If no room is reachable, return [-1, -1].

Because every move costs 1, the grid is an unweighted graph, so a Breadth-First Search from the start visits cells in nondecreasing distance order. The first cell with value 2 that BFS dequeues is a closest room. If multiple rooms are tied for the minimum distance, the one returned is the first reached in BFS order using the neighbor order down, up, right, left.

Example: for grid [[0,0,1,0],[0,2,1,0],[0,2,1,0]] and start [0,0], the output is [1,1].

Constraints

• 1 <= m, n <= 1000
• grid[i][j] is one of 0 (empty), 1 (wall), 2 (meeting room)
• start is within bounds; if start is on a wall, return [-1, -1]
• If the start cell itself is a room (value 2), distance is 0 and that cell is returned

Hints

1. Equal move cost means an unweighted graph: BFS, not Dijkstra, finds shortest distances.
2. Mark cells visited the moment you enqueue them so you never revisit, and never step onto a wall (value 1).
3. The first dequeued cell whose value is 2 is a nearest room — return immediately.
4. Handle the edge cases: start on a wall, start already on a room, and no room reachable at all (return [-1, -1]).

Best Meeting Room for Two Users (Min Distance Sum)

Same grid encoding as before: 1 is a wall, 0 is empty, 2 is a meeting room, and moves cost 1 step in the four cardinal directions. Now you are given two starting coordinates, s1 and s2. Return the meeting room that minimizes the sum of the two users' shortest-path distances to it, considering only rooms reachable by BOTH users, together with that minimum total distance.

Return the answer as [[row, col], totalDistance]. If no room is reachable by both users, return [[-1, -1], -1].

Approach: run one BFS from each start to compute every cell's shortest distance (-1 for unreachable cells). Then scan all room cells; for each room reachable by both (d1 != -1 and d2 != -1), compute d1 + d2 and keep the minimum. Ties are broken by row-major scan order (smallest row, then smallest column).

Example: for grid [[0,0,1,0],[0,2,1,0],[0,2,1,0]] with s1 = [0,0] and s2 = [2,0], room [1,1] gives total distance 2 + 2 = 4, the minimum, so the output is [[1,1], 4].

Constraints

• 1 <= m, n <= 1000
• grid[i][j] is one of 0 (empty), 1 (wall), 2 (meeting room)
• s1 and s2 are within bounds (each may coincide with a room or with each other)
• Only rooms reachable by BOTH users are candidates
• Ties in total distance are broken by row-major order (smallest row, then column)

Hints

1. Run one BFS per user to get full distance maps; do not run a fresh search per room.
2. Use -1 to mark unreachable cells so a single check (d1 != -1 and d2 != -1) enforces 'reachable by both'.
3. After both BFS runs, scan every room cell once and minimize d1 + d2.
4. If no room is reachable by both, the answer is [[-1, -1], -1] — initialize the best total to -1 and only update on a valid candidate.