[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

思路：

这题题意也略显含糊，实际上就是要将所有以O组成、但不连通到网格边缘的区域变为X。所以我们可以先在四边上寻找连通到边缘的区域，将它们的O都变成Y。剩余的所有O一定无法连通到边缘，所以可以全部变为X。最后再将所有Y变回O。

这题的测试比较tricky，上来没多想就用递归的DFS实现flood fill，结果发现run time error，栈溢出了：

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<vector<char>> &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<vector<char>> &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<vector<char>> &board, char target, char c) { int m = board.size(), n = board[0].size(); for(int i=0; i<m; i++) { if(board[i][0]==target) fill(board, i, 0, target, c); if(board[i][n-1]==target) fill(board, i, n-1, target, c); } for(int j=1; j<n-1; j++) { if(board[0][j]==target) fill(board, 0, j, target, c); if(board[m-1][j]==target) fill(board, m-1, j, target, c); } } void replace(vector<vector<char>> &board, char target, char c) { int m = board.size(), n = board[0].size(); for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { if(board[i][j]==target) board[i][j] = c; } } } };

于是些了个迭代版的DFS，果然过了大数据测试。当然这里也可以用BFS实现flood fill。

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<vector<char>> &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<vector<char>> &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<pair<int,int>> 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(i<m-1 && board[i+1][j]==target) s.push(make_pair(i+1,j)); if(j>0 && board[i][j-1]==target) s.push(make_pair(i,j-1)); if(j<n-1 && board[i][j+1]==target) s.push(make_pair(i,j+1)); } } void fillBorders(vector<vector<char>> &board, char target, char c) { int m = board.size(), n = board[0].size(); for(int i=0; i<m; i++) { if(board[i][0]==target) fill(board, i, 0, target, c); if(board[i][n-1]==target) fill(board, i, n-1, target, c); } for(int j=1; j<n-1; j++) { if(board[0][j]==target) fill(board, 0, j, target, c); if(board[m-1][j]==target) fill(board, m-1, j, target, c); } } void replace(vector<vector<char>> &board, char target, char c) { int m = board.size(), n = board[0].size(); for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { if(board[i][j]==target) board[i][j] = c; } } } };