#130

Surrounded Regions

medium · 44.8% accepted · 9,818 likes · top 27%

array · depth-first search · breadth-first search · union-find · matrix

⊣ practice⊣ quiz⊣ open on leetcode ↗

Description

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

 - Connect: A cell is connected to adjacent cells horizontally or vertically.

 - Region: To form a region connect every 'O' cell.

 - Surround: A region is surrounded if none of the 'O' cells in that region are on the edge of the board. Such regions are completely enclosed by 'X' cells.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

Solution