LeetCode 130. Surrounded Regions

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]Explanation: Notice that an 'O' should not be flipped if: - It is on the border, or - It is adjacent to an 'O' that should not be flipped. The bottom 'O' is on the border, so it is not flipped. The other three 'O' form a surrounded region, so they are flipped.

Example 2:

Input: board = [["X"]]Output: [["X"]]

Constraints:

• m == board.length

• n == board[i].length

• 1 <= m, n <= 200

• board[i][j] is 'X' or 'O'.

典型的DFS先将边上的为O的改成#，然后dfs跟他相关联的位置也一并改成#，剩下的O就是呗X包围着的，然后2个for循环就可以了。

Runtime: 4 ms, faster than 63.84% of Java online submissions for Surrounded Regions.

Memory Usage: 52.7 MB, less than 13.82% of Java online submissions for Surrounded Regions.

Next challenges:

Walls and Gates