Graphs Grids as graphs
437. Surrounded Regions
You are given a board of X and O cells as a list of strings, board. board[i] is row i, and
board[i][j] is the cell in row i, column j.
A region is a group of O cells joined by steps up, down, left or right. A region is surrounded
when none of its cells is on the edge of the board. Capture every surrounded region by turning all of its
cells into X. A region with at least one cell on the edge stays as it is.
Return the board after capturing, as a list of strings of the same size.
Example 1
Input: board = ["XXXXO",
"XOOXO",
"XXOXX",
"XOXXX",
"XOXXX"]
["XXXXO","XXXXO","XXXXX","XOXXX","XOXXX"]Explanation: The three O's in the middle have no cell on the edge, so they become X. The pair on the right reaches the top edge, and the pair at the bottom left reaches the bottom edge, so both stay.
Example 2
Input: board = ["XOX", "XOX", "XOX"]
["XOX","XOX","XOX"]Explanation: The middle O is not on the edge, but it is joined to the O's above and below it, which are. The column is one region that reaches the edge, so nothing changes.
Example 3
Input: board = ["XXX", "XOX", "XXX"]
["XXX","XXX","XXX"]Explanation: The single O has no cell on the edge, so it is captured.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
m == board.length,n == board[i].length1 ≤ m, n ≤ 300board[i][j]isXorO.
Clarifying questions
What you would ask an interviewer before writing any code.