## Sunday, March 3, 2013

### [LeetCode] Surrounded Regions, Solution

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
```
» Solve this problem

[解题思路]

``````1:    vector<int> xIndex;
2:    vector<int> yIndex;
3:    map<int, int> visited;
4:    void solve(vector<vector<char>> &board) {
5:      int row = board.size();
6:      if(row == 0) return;
7:      int col = board[0].size();
8:      for(int i =0; i < row; i++)
9:      {
10:        for(int j =0; j< col; j++)
11:        {
12:          if(board[i][j] == 'X' || IsVisited(i*row+j)) continue;
13:          visited.clear();
14:          bool surranded = true;
15:          xIndex.clear();
16:          xIndex.push_back(i);
17:          yIndex.clear();
18:          yIndex.push_back(j);
19:          int k =0;
20:          while(k<xIndex.size())
21:          {
22:            int x = xIndex[k];
23:            int y = yIndex[k];
24:            visited[x*row +y] =1;
25:            if(IsInBoundary(x, y, row, col)) surranded = false;
26:            if(x<row-1 && board[x+1][y] == 'O' && !IsVisited((x+1)*row+y)) {xIndex.push_back(x+1); yIndex.push_back(y);}
27:            if(y<col-1 && board[x][y+1] == 'O' && !IsVisited(x*row+y+1)) {xIndex.push_back(x); yIndex.push_back(y+1);}
28:            k++;
29:          }
30:          if(surranded) //clean the surranded mask
31:          {
32:            for(int m = 0; m<xIndex.size(); m++)
33:            {
34:              board[xIndex[m]][yIndex[m]] = 'X';
35:            }
36:          }
37:        }
38:      }
39:    }
40:    bool IsInBoundary(int x, int y, int row, int col)
41:    {
42:      if(x ==0 || x == row-1) return true;
43:      if(y ==0 || y == col-1) return true;
44:      return false;
45:    }
46:    bool IsVisited(int index)
47:    {
48:      if(visited.find(index) == visited.end()) return false;
49:      return true;
50:    }
``````

1. 从四条边上的O元素开始BFS，所有相连的O都赋个新值，比如‘Y’
2. 扫描整个数组，所有现存的O元素全部置为X，所有Y元素置为O

``````1:       vector<int> xIndex;
2:       vector<int> yIndex;
3:       void solve(vector<vector<char>> &board) {
4:            int row = board.size();
5:            if(row == 0) return;
6:            int col = board[0].size();
7:            xIndex.clear();
8:            yIndex.clear();
9:            for(int i =0; i< row; i++)
10:            {
11:                 if(board[i][0] == 'O')
12:                 {
13:                      xIndex.push_back(i);
14:                      yIndex.push_back(0);
15:                 }
16:                 if(board[i][col-1] == 'O')
17:                 {
18:                      xIndex.push_back(i);
19:                      yIndex.push_back(col-1);
20:                 }
21:            }
22:            for(int i =0; i< col; i++)
23:            {
24:                 if(board[0][i] == 'O')
25:                 {
26:                      xIndex.push_back(0);
27:                      yIndex.push_back(i);
28:                 }
29:                 if(board[row-1][i] == 'O')
30:                 {
31:                      xIndex.push_back(row-1);
32:                      yIndex.push_back(i);
33:                 }
34:            }
35:            int k =0;
36:            while(k<xIndex.size())
37:            {
38:                 int x = xIndex[k];
39:                 int y = yIndex[k];
40:                 board[x][y] = 'Y';
41:                 if(x>0 && board[x-1][y] == 'O' ) {xIndex.push_back(x-1); yIndex.push_back(y);}
42:                 if(x<row-1 && board[x+1][y] == 'O' ) {xIndex.push_back(x+1); yIndex.push_back(y);}
43:                 if(y>0 && board[x][y-1] == 'O' ) {xIndex.push_back(x); yIndex.push_back(y-1);}
44:                 if(y<col-1 && board[x][y+1] == 'O' ) {xIndex.push_back(x); yIndex.push_back(y+1);}
45:                 k++;
46:            }
47:            for(int i =0; i< row; i++)
48:            {
49:                 for(int j =0; j< col; j++)
50:                 {
51:                      if(board[i][j] =='O') board[i][j] = 'X';
52:                      if(board[i][j] == 'Y') board[i][j] = 'O';
53:                 }
54:            }
55:       }
``````