Proficient Level
Implement the surroundedRegionsSafeCount method that counts cells not captured in a surrounded-regions board.
You are given a board represented by 0 and 1. Treat 1 as an open cell and 0 as a blocked cell.
An open cell is safe if it is connected to the border through other open cells. Open cells completely surrounded by blocked cells are captured. Return the number of safe open cells.
Example 1
Input
board (int[][]) =
[[0,0,0,0],[0,1,1,0],[0,0,1,0],[0,1,0,0]]rows (int) =
4cols (int) =
4Returns (int)
1Example 2
Input
board (int[][]) =
[[1,1],[1,1]]rows (int) =
2cols (int) =
2Returns (int)
4Example 3
Input
board (int[][]) =
[[0,1,0],[1,1,1],[0,1,0]]rows (int) =
3cols (int) =
3Returns (int)
5The safe cells are exactly the open cells connected to the border.
Start DFS or BFS from every border cell that contains 1. Mark every reachable open cell as safe. After all border searches finish, count how many cells were marked safe.
This avoids checking each region separately and directly finds the cells that cannot be captured.
Pseudocode:
function surroundedRegionsSafeCount(board, rows, cols):
visited = matrix filled with false
for each border cell:
if board[cell] == 1 and not visited[cell]:
run DFS from that cell and mark reachable 1 cells
count = 0
for each cell:
if visited[cell] is true:
count++
return countReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run