Surrounded Regions

Problem

Given a board of X and O characters, return a copy where every region of O completely surrounded by X is flipped to X, while regions touching the border stay O.

Flood fill from all border Os marking them safe, then flip every unmarked O to X and restore the safe marks. Return the resulting board.

Hint

A temporary marker distinguishes border-connected Os from captured ones.

Test cases

case 1

in: [[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]]

expected: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

case 2

in: [[["X"]]]

expected: [["X"]]

case 3

in: [[["O"]]]

expected: [["O"]]

case 4

in: [[["O","O"],["O","O"]]]

expected: [["O","O"],["O","O"]]

case 5

in: [[["X","X","X"],["X","O","X"],["X","X","X"]]]

expected: [["X","X","X"],["X","X","X"],["X","X","X"]]

Starter codePython

def solve_surrounded(board):
    # Your code here
    pass

5 test cases · run your code against them in the editor