You are given a robot placed inside a room that must clean every empty cell it can reach.
The room is represented as an m x n grid. A value of 1 represents an empty cell that can be visited and cleaned, while a value of 0 represents a wall that blocks movement.
The robot starts on an empty cell at position startRow and startCol.
The robot can move only in four directions: up, right, down, and left.
Your task is to find how many reachable empty cells the robot can clean.
Robot Movement Rules
- The robot can move from its current cell to one of its four neighboring cells.
- The robot can move up, right, down, or left.
- The robot cannot move diagonally.
- The robot can enter only cells with value
1.
- The robot cannot enter cells with value
0.
- The robot cleans each reachable empty cell exactly once.
Method Signature
Implement the following method:
int cleanRoom(List<String> room, int startRow, int startCol)
room represents the room grid.- Each string in
room represents one row of the room.
- Values inside each row are separated by commas.
startRow is the row where the robot starts.startCol is the column where the robot starts.- Return the number of reachable empty cells that the robot can clean.
- You must never use
null as a parameter value.
Important Details
- The robot always starts on an empty cell.
- All boundary cells of the room are walls.
- The robot must clean every empty cell that is reachable from its starting cell.
- Empty cells that are completely separated by walls from the starting cell do not need to be cleaned.
- A cell is reachable only if there is a path of adjacent empty cells from the starting cell to that cell.
- Two cells are adjacent only if they share a side horizontally or vertically.
Input Format
The room is given as a List<String>.
Each string represents one row of the room, and values are separated by commas.
For example, "1,0,1" represents a row with an empty cell, then a wall, then an empty cell.
Constraints
3 ≤ m ≤ 1003 ≤ n ≤ 200room.size() == m- Each row contains exactly
n comma-separated values.
- Each cell is either
0 or 1.
0 ≤ startRow < m0 ≤ startCol < nroom[startRow][startCol] == 1- All boundary cells of the room are walls.
- The number of reachable empty cells is at most
20,000.
Examples
Example 1
Method call:
cleanRoom(room = ["0,0,0,0,0", "0,1,1,1,0", "0,1,0,1,0", "0,1,1,1,0", "0,0,0,0,0"], startRow = 1, startCol = 1)
Output:
8
Explanation:
The center cell is a wall. The robot starts at an empty cell connected to the other 7 empty cells around the center wall, so all 8 reachable empty cells are cleaned.
Example 2
Method call:
cleanRoom(room = ["0,0,0,0", "0,1,0,0", "0,1,1,0", "0,0,0,0"], startRow = 1, startCol = 1)
Output:
3
Explanation:
The reachable empty cells are the starting cell at (1,1), the cell below it at (2,1), and the cell to the right at (2,2).
Example 3
Method call:
cleanRoom(room = ["0,0,0", "0,1,0", "0,0,0"], startRow = 1, startCol = 1)
Output:
1
Explanation:
The robot starts on the only empty cell, and all four neighboring cells are walls.
Example 4
Method call:
cleanRoom(room = ["0,0,0,0,0,0", "0,1,1,0,1,0", "0,0,1,0,1,0", "0,1,1,1,1,0", "0,0,0,0,0,0"], startRow = 1, startCol = 1)
Output:
9
Explanation:
The reachable empty cells are connected through a narrow path: (1,1), (1,2), (2,2), (3,2), (3,1), (3,3), (3,4), (2,4), and (1,4). Therefore, all 9 reachable empty cells are cleaned.
Example 5
Method call:
cleanRoom(room = ["0,0,0,0,0,0,0", "0,1,1,0,1,1,0", "0,1,0,0,0,1,0", "0,1,1,1,0,1,0", "0,0,0,0,0,0,0"], startRow = 1, startCol = 1)
Output:
6
Explanation:
The robot can reach and clean the left connected component containing (1,1), (1,2), (2,1), (3,1), (3,2), and (3,3). The empty cells on the right side are separated by walls, so they are not reachable from the starting cell and do not need to be cleaned.