[Leetcode][JAVA] Surrounded Regions

浏览数：24 / 时间：2015年06月08日

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.

For example,

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

After running your function, the board should be:

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


基本思路是：如果把所有不该变为X的O标注出来，那么剩下的O就是要变为X的了。
所以，从矩阵各个边上的O开始进行图的遍历，入栈/队列时把相应节点值从‘O‘变成其他符号（我用的是‘+‘）,出栈/队列时对节点四方的相邻值为‘O‘的节点进行讨论。
全部遍历完后，把‘O‘变为‘X‘， ‘+‘变为‘O‘。
代码：

 1 public class Pair {
 2         int x;
 3         int y;
 4         Pair(int x, int y) {
 5             this.x = x;
 6             this.y = y;
 7         }
 8     }
 9     public void solve(char[][] board) {
10         int m=board.length;
11         if(m<=2)
12             return;
13         int n=board[0].length;
14         for(int i=0;i<m;i++) {
15             if(board[i][0]==‘O‘)
16                 dfs(board, i, 0);
17             if(board[i][n-1]==‘O‘)
18                 dfs(board, i, n-1);
19         }
20         for(int i=0;i<n;i++) {
21             if(board[0][i]==‘O‘)
22                 dfs(board, 0, i);
23             if(board[m-1][i]==‘O‘)
24                 dfs(board, m-1, i);
25         }
26         for(int i=0;i<m;i++)
27             for(int j=0;j<n;j++) {
28                 if(board[i][j]==‘O‘)
29                     board[i][j]=‘X‘;
30                 else if(board[i][j]==‘+‘)
31                     board[i][j]=‘O‘;
32             }
33     }
34     public void dfs(char[][] bd, int i, int j)
35     {
36         Stack<Pair> st = new Stack<Pair>();
37         bd[i][j] = ‘+‘;
38         st.push(new Pair(i,j));
39         
40         while(!st.isEmpty()) {
41             Pair temp = st.pop();
42             if(temp.x>0 && bd[temp.x-1][temp.y]==‘O‘) {
43                 bd[temp.x-1][temp.y]=‘+‘;
44                 st.push(new Pair(temp.x-1, temp.y));
45             }
46             if(temp.y<bd[0].length-1 && bd[temp.x][temp.y+1]==‘O‘) {
47                 bd[temp.x][temp.y+1]=‘+‘;
48                 st.push(new Pair(temp.x, temp.y+1));
49             }
50             if(temp.x<bd.length-1 && bd[temp.x+1][temp.y]==‘O‘) {
51                 bd[temp.x+1][temp.y]=‘+‘;
52                 st.push(new Pair(temp.x+1, temp.y));
53             }
54             if(temp.y>0 && bd[temp.x][temp.y-1]==‘O‘) {
55                 bd[temp.x][temp.y-1]=‘+‘;
56                 st.push(new Pair(temp.x, temp.y-1));
57             }
58         }
59     }