Surrounded Regions
MediumThe problem
board contains "X" and "O". A region is a group of "O" cells connected up, down, left or right. A region is surrounded if none of its cells is on the edge of the board. Change the board in place so that every surrounded region of "O" turns into "X".
- Example 1Input: board = [["X", "X", "X", "X"], ["X", "O", "O", "X"], ["X", "X", "O", "X"], ["X", "O", "X", "X"]]Output: board becomes [["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "O", "X", "X"]]
The three connected "O" cells in the middle never touch the edge, so they flip. The "O" on the bottom edge stays.
- Example 2Input: board = [["O"]]Output: board stays [["O"]]
The only cell is on the edge.
- 1 ≤ rows, columns ≤ 200
- Each cell is the byte "X" or "O"
- The function returns nothing; it edits board
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Which O cells are definitely safe? The ones touching the border and anything connected to them.
The idea
Flood-fill from border O cells marking them safe; then flip every remaining O to X and restore the safe ones.
Target: O(m·n) time
Go function shape
func solve(board [][]byte)Reference solution
Tested with go test. Try it yourself first, then compare.
// Solve flips every 'O' region that is completely surrounded by 'X'. The regions that must NOT flip are the ones
// touching the border, so mark those safe first ('S'), then flip what is left and restore the safe ones.
func Solve(board [][]byte) {
rows, cols := len(board), len(board[0])
var mark func(r, c int)
mark = func(r, c int) {
if r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != 'O' {
return
}
board[r][c] = 'S'
mark(r+1, c)
mark(r-1, c)
mark(r, c+1)
mark(r, c-1)
}
for r := 0; r < rows; r++ {
mark(r, 0)
mark(r, cols-1)
}
for c := 0; c < cols; c++ {
mark(0, c)
mark(rows-1, c)
}
for r := range board {
for c := range board[r] {
switch board[r][c] {
case 'O':
board[r][c] = 'X' // surrounded
case 'S':
board[r][c] = 'O' // touched the border: restore
}
}
}
}