AceYourInterviews
Checking sign-in…

99. Surrounded Regions

CoreCertify boundary-connected open cells, then capture the complement

Identify groups of orthogonally connected O cells. Change a group to X only if it has no O path leading to any edge of the board.

An O region connected to the boundary remains O, even if some of its cells lie deep inside the board. Diagonal paths do not count.

Example 1

Input

[XXXX,XOOX,XXOX,XOXX]

Output

[XXXX,XXXX,XXXX,XOXX]

Explanation: The three upper interior O cells are enclosed; the bottom O is a boundary seed.

Example 2

Input

[XOXX,XOOX,XXOX,XXXX]

Output

unchanged board

Explanation: The interior component has an O path to the top boundary even though most of it is not itself on the edge.

Constraints

  • 0 <= board.length <= 105
  • 0 <= total board cells <= 105
  • All rows have equal length and are non-null.
  • Cells are 'X' or 'O'.
Hints
Hint 1

Which O cells are definitely not surrounded?

Hint 2

Start from all boundary O cells and mark everything they can reach.

Hint 3

After that traversal, change exactly the remaining O cells to X.

Practice on LeetCode ↗
Code
Saved on this deviceLn 1, Col 1

Boundary certification precedes capture

["XXXX","XOOX","XXOX","XOXX"]
["XXXX","XXXX","XXXX","XOXX"]