130. Surrounded Regions

beiyeqingteng 2021-08-30 原文

Given a 2D board containing \'X\' and \'O\', capture all regions surrounded by \'X\'.

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

Example

X X X X
X O O X
X X O X
X O X X

After capture all regions surrounded by \'X\', the board should be:

X X X X
X X X X
X X X X
X O X X

分析：
我们知道O能否变成X，我们需要检查是否边框上有O能够和它链接，如果不能，这需要变成X。所以我们可以从边框开始，DFS搜索。

 1 public class Solution {
 2     /**
 3      * @param board a 2D board containing \'X\' and \'O\'
 4      * @return void
 5      */
 6     public void surroundedRegions(char[][] board) {
 7         if (board == null || board.length <= 1 || board[0].length <= 1) return;
 8         
 9         boolean[][] visited = new boolean[board.length][board[0].length];
10         //上下边
11         for (int i = 0; i < board[0].length; i++) {
12                 helper(board, 0, i, visited);
13                 helper(board, board.length - 1, i, visited);
14         }
15         //左右边
16         for (int i = 0; i < board.length; i++) {
17             helper(board, i, 0, visited);
18             helper(board, i, board[0].length - 1, visited);
19         }
20         // 如果O没有被visited,那么我们就只能把它转成X
21         for (int i = 1; i < board.length; i++) {
22             for (int j = 1; j < board[0].length; j++) {
23                 if (board[i][j] == \'O\' && visited[i][j] == false) {
24                     board[i][j] = \'X\';
25                 }
26             }
27         }
28     }
29     
30     public void helper(char[][] board, int i, int j, boolean[][] visited) {
31         if (i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1 || board[i][j] == \'X\' || visited[i][j] == true) {
32             return;
33         }
34         visited[i][j] = true;
35         
36         helper(board, i - 1, j, visited);
37         helper(board, i + 1, j, visited);
38         helper(board, i, j - 1, visited);
39         helper(board, i, j + 1, visited);
40     }
41 }

但是，当array的size很大的时候，很明显会产生stack overflow. 所以，递归这种方法可能不是面试官想要的。

对于非递归方法，我们需要把当前点加入到一个序列里

 1 import java.util.LinkedList;
 2 import java.util.Queue;
 3 
 4 public class Solution {
 5     /**
 6      * @param board
 7      *            a 2D board containing \'X\' and \'O\'
 8      * @return void
 9      */
10 
11     public void solve(char[][] board) {
12         if (board == null || board.length <= 1 || board[0].length <= 1)
13             return;
14 
15         for (int i = 0; i < board[0].length; i++) {
16             helper(board, 0, i);
17             helper(board, board.length - 1, i);
18         }
19         // 左右边
20         for (int i = 0; i < board.length; i++) {
21             helper(board, i, 0);
22             helper(board, i, board[0].length - 1);
23         }
24 
25         for (int i = 0; i < board.length; i++) {
26             for (int j = 0; j < board[0].length; j++) {
27                 if (board[i][j] == \'O\') {
28                     board[i][j] = \'X\';
29                 } else if (board[i][j] == \'#\') {
30                     board[i][j] = \'O\';
31                 }
32             }
33         }
34 
35     }
36 
37     public void helper(char[][] board, int i, int j) {
38         if (board[i][j] != \'O\') {
39             return;
40         }
41         Queue<Point> queue = new LinkedList<Point>();
42         board[i][j] = \'#\';
43         queue.offer(new Point(i, j));
44 
45         while (queue.size() != 0) {
46             Point p = queue.poll();
47             int x = p.x;
48             int y = p.y;
49             if (x - 1 >= 0 && board[x - 1][y] == \'O\') {
50                 queue.offer(new Point(x - 1, y));
51                 board[x - 1][y] = \'#\';  // cannot be omited, otherwise, it may have infinite loop.
52             }
53 
54             if (x + 1 <= board.length - 1 && board[x + 1][y] == \'O\') {
55                 queue.offer(new Point(x + 1, y));
56                 board[x + 1][y] = \'#\';
57             }
58 
59             if (y - 1 >= 0 && board[x][y - 1] == \'O\') {
60                 queue.offer(new Point(x, y - 1));
61                 board[x][y - 1] = \'#\';
62             }
63 
64             if (y + 1 <= board[0].length - 1 && board[x][y + 1] == \'O\') {
65                 queue.offer(new Point(x, y + 1));
66                 board[x][y + 1] = \'#\';
67             }
68         }
69     }
70 
71 }
72 class Point {
73     int x;
74     int y;
75 
76     public Point(int x, int y) {
77         this.x = x;
78         this.y = y;
79     }
80 }