[Leetcode] surrounded regions

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 '全部换成' X '，只要有一边没有被包围都保持原样。

方法一：DFS，从四周边界开始遇到' O '，就好奇紧邻的元素是否为' O '，然后最后到哪了，判断完一条再去判断另一条，这样整个深搜的思想出来了。参考了Coder Gander。网上关于DFS的一般思路，就是遇到不符和转换要求的' O '先将其换成别的字符（非X），然后最后遍历一次矩阵，遇到' O '换成' X '，遇到别的字符，换成' O '，即可。代码如下：

 1 class Solution {
 2 public:
 3     void solve(vector<vector<char>> &board) 
 4     {
 5         int row=board.size();
 6         int col=board[0].size();
 7 
 8         if(row<1||col<1)    return;
 9 
10         for(int i=0;i<row;++i)  //两侧　　　　两侧和上下的深搜可以用两个for循环和一个if条件判断合并
11         {
12             dfs(board,i,0);
13             dfs(board,i,col-1);
14         }    
15 
16         for(int i=0;i<col;++i)  //上下
17         {
18             dfs(board,0,i);
19             dfs(board,row-1,i);
20         }
21 
22         for(int i=0;i<row;++i)
23             for(int j=0;j<col;++j)
24             {
25                 if(board[i][j]=='*')
26                     board[i][j]='O';
27                 else
28                     board[i][j]='X';
29             }
30     }
31 
32     void dfs(vector<vector<char>> &board,int irow,int jcol)
33     {
34         if(board[irow][jcol]=='O')
35         {
36             board[irow][jcol]='*';
37 
38             if(irow<board.size()-1)     //下
39                 dfs(board,irow+1,jcol);
40             if(jcol<board[0].size()-1)  //右
41                 dfs(board,irow,jcol+1);
42             if(irow>1)                  //上
43                 dfs(board,irow-1,jcol);
44             if(jcol>1)                  //左
45                 dfs(board,irow,jcol-1);
46         }
47     }
48 };

方法二：BFS，用队列去存放矩阵中元素的下标，以该下标为基础进行广度遍历。参考a83610312，针对他博客中讲的精简代码的方案，参考哎-哭泣的鱼（这里的代码还是没有精简）。

 1 class Solution {
 2 public:
 3     void solve(vector<vector<char>> &board) 
 4     {
 5         int row=board.size();
 6         int col=board[0].size();
 7 
 8         if(row<3||col<3)  return;
 9 
10         for(int i=0;i<row;++i)
11             for(int j=0;j<col;++j)
12             {
13                 if((board[i][j]=='O')&&(i==0||i==row-1||j==0||j==col-1))
14                     BFS(board,i,j);
15             }
16         
17         for(int i=0;i<row;++i)
18             for(int j=0;j<col;++j)
19             {
20                 if(board[i][j]=='O')
21                     board[i][j]='X';
22                 else if(board[i][j]=='*')
23                     board[i][j]='O';
24             }
25         
26     }
27 
28     void BFS(vector<vector<char>> &board,int i,int j)
29     {
30         board[i][j]='*';
31 
32         int m=board.size();
33         int n=board[0].size();
34         typedef pair<int,int> cooPoint;
35 
36         queue<cooPoint> q;
37         q.push(cooPoint(i,j));
38 
39         while( !q.empty())
40         {
41             cooPoint temp=q.front();
42             q.pop();
43 
44             int x=temp.first,y=temp.second;
45 
46             if(x>0&&board[x-1][y]=='O')
47             {
48                 q.push(cooPoint(x-1,y));
49                 board[x-1][y]='*';
50             }
51             if(x<m-1&&board[x+1][y]=='O')
52             {
53                 q.push(cooPoint(x+1,y));
54                 board[x+1][y]='*';
55             }
56             if(y>0&&board[x][y-1]=='O')
57             {
58                 q.push(cooPoint(x,y-1));
59                 board[x][y-1]='*';
60             }
61             if(y<n-1&&board[x][y+1]=='O')
62             {
63                 q.push(cooPoint(x,y+1));
64                 board[x][y+1]='*';
65             }
66         }
67 
68     }
69 };