## Monday, November 24, 2014

### [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```

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43``` ```class Solution { public: void solve(vector> &board) { if(board.size()<3 || board[0].size()<3) return; fillBorders(board, 'O', 'Y'); replace(board, 'O', 'X'); fillBorders(board, 'Y', 'O'); } void fill(vector> &board, int i, int j, char target, char c) { int m = board.size(), n = board[0].size(); if(i<0 || j<0 || i>=m || j>=n || board[i][j]!=target) return; board[i][j] = c; fill(board, i-1, j, target, c); fill(board, i+1, j, target, c); fill(board, i, j-1, target, c); fill(board, i, j+1, target, c); } void fillBorders(vector> &board, char target, char c) { int m = board.size(), n = board[0].size(); for(int i=0; i> &board, char target, char c) { int m = board.size(), n = board[0].size(); for(int i=0; i

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51``` ```class Solution { public: void solve(vector> &board) { if(board.size()<3 || board[0].size()<3) return; fillBorders(board, 'O', 'Y'); replace(board, 'O', 'X'); fillBorders(board, 'Y', 'O'); } void fill(vector> &board, int i, int j, char target, char c) { int m = board.size(), n = board[0].size(); if(i<0 || j<0 || i>=m || j>=n || board[i][j]!=target) return; stack> s; s.push(make_pair(i,j)); while(!s.empty()) { i = s.top().first; j = s.top().second; s.pop(); board[i][j] = c; if(i>0 && board[i-1][j]==target) s.push(make_pair(i-1,j)); if(i0 && board[i][j-1]==target) s.push(make_pair(i,j-1)); if(j> &board, char target, char c) { int m = board.size(), n = board[0].size(); for(int i=0; i> &board, char target, char c) { int m = board.size(), n = board[0].size(); for(int i=0; i