首页 > 代码库 > Surrounded Regions
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 XX O O XX X O XX O X X
After running your function, the board should be:
X X X XX X X XX X X XX O X X
这道题目最大的误区是想办法去找被包围的O，搜索的过程会过于复杂，如果能够逆向的求解，题目将变得非常容易。思路就是，去搜索不会被X包围的O，将其置为一个特殊字符，然后把剩下的O置为X，再把特殊字符恢复成O即可。
细化下来，去思考怎样的O不会被X包围，在边界的不会被包围，或者与不会被包围的相连，这不就变成了搜索的问题了么，从4个boundary入手，搜索这个矩阵，找到不会被包围的O。
这个题目用到的方法是图形学中的一个常用方法：Flood fill算法，其实就是从一个点出发对周围区域进行目标颜色的填充。背后的思想就是把一个矩阵看成一个图的结构，每个点看成结点，而边则是他上下左右的相邻点，然后进行一次广度或者深度优先搜索。
接下来我们看看这个题如何用Flood fill算法来解决。首先根据题目要求，边缘上的‘O‘是不需要填充的，所以我们的办法是对上下左右边缘做Flood fill算法，把所有边缘上的‘O‘都替换成另一个字符，比如‘#‘。接下来我们知道除去被我们换成‘#‘的那些顶点，剩下的所有‘O‘都应该被替换成‘X‘，而‘#‘那些最终应该是还原成‘O‘，如此我们可以做最后一次遍历，然后做相应的字符替换就可以了。复杂度分析上，我们先对边缘做Flood fill算法，因为只有是‘O‘才会进行，而且会被替换成‘#‘，所以每个结点改变次数不会超过一次，因而是O(m*n)的复杂度，最后一次遍历同样是O(m*n)，所以总的时间复杂度是O(m*n)。空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是n/2*2+m/2*2=m+n，所以算法的空间复杂度是O(m+n)）。
接下来我们看看这个题如何用Flood fill算法来解决。首先根据题目要求，边缘上的‘O‘是不需要填充的，所以我们的办法是对上下左右边缘做Flood fill算法，把所有边缘上的‘O‘都替换成另一个字符，比如‘#‘。接下来我们知道除去被我们换成‘#‘的那些顶点，剩下的所有‘O‘都应该被替换成‘X‘，而‘#‘那些最终应该是还原成‘O‘，如此我们可以做最后一次遍历，然后做相应的字符替换就可以了。复杂度分析上，我们先对边缘做Flood fill算法，因为只有是‘O‘才会进行，而且会被替换成‘#‘，所以每个结点改变次数不会超过一次，因而是O(m*n)的复杂度，最后一次遍历同样是O(m*n)，所以总的时间复杂度是O(m*n)。空间上就是递归栈（深度优先搜索）或者是队列（广度优先搜索）的空间，同时存在的空间占用不会超过O(m+n)（以广度优先搜索为例，每次队列中的结点虽然会往四个方向拓展，但是事实上这些结点会有很多重复，假设从中点出发，可以想象最大的扩展不会超过一个菱形，也就是n/2*2+m/2*2=m+n，所以算法的空间复杂度是O(m+n)）。
参考：http://blog.csdn.net/linhuanmars/article/details/22904855
应用广度优先遍历实现C++代码：
#include<iostream>#include<vector>#include<queue>using namespace std;class Solution{public: void solve(vector<vector<char>> &board) { if(board.empty()||board[0].empty()) return; int row=board.size(); int col=board[0].size(); int i,j; for(i=0; i<row; i++) { bfs(i,0,board); bfs(i,col-1,board); } for(j=0; j<col; j++) { bfs(0,j,board); bfs(row-1,j,board); } for(i=0; i<row; i++) { for(j=0; j<col; j++) { if(board[i][j]==‘O‘) board[i][j]=‘X‘; else if(board[i][j]==‘#‘) board[i][j]=‘O‘; } } } void bfs(int i,int j,vector<vector<char> > &board) { if(board[i][j]!=‘O‘) return; board[i][j]=‘#‘; queue<int> q; int line=i*board[0].size()+j; q.push(line); while(!q.empty()) { line=q.front(); q.pop(); int row=line/board[0].size(); int col=line%board[0].size(); if(row>0&&board[row-1][col]==‘O‘) { board[row-1][col]=‘#‘; q.push((row-1)*board[0].size()+col); } if(row<board.size()-1&&board[row+1][col]==‘O‘) { board[row+1][col]=‘#‘; q.push((row+1)*board[0].size()+col); } if(col>0&&board[row][col-1]==‘O‘) { board[row][col-1]=‘#‘; q.push(row*board[0].size()+col-1); } if(col<board[0].size()-1&&board[row][col+1]==‘O‘) { board[row][col+1]=‘#‘; q.push(row*board[0].size()+col+1); } } }};int main(){ Solution s; vector<vector<char> > vec={{‘X‘,‘X‘,‘X‘,‘X‘},{‘X‘,‘O‘,‘O‘,‘X‘},{‘X‘,‘X‘,‘O‘,‘X‘},{‘X‘,‘O‘,‘X‘,‘X‘}}; //vector<vector<char> > vec={{‘O‘,‘O‘,‘O‘,‘O‘},{‘O‘,‘O‘,‘O‘,‘O‘},{‘O‘,‘O‘,‘O‘,‘O‘},{‘O‘,‘O‘,‘O‘,‘O‘}}; s.solve(vec); for(auto a:vec) { for(auto v:a) cout<<v<<" "; cout<<endl; }}
运行结果：
应用dfs，通不过大集合。
#include<iostream>#include<vector>using namespace std;class Solution {public: void solve(vector<vector<char>> &board) { if(board.empty()||board[0].empty()) return; int row=board.size(); int col=board[0].size(); int i,j; for(i=0;i<row;i++) { dfs(i,0,board); dfs(i,col-1,board); } for(j=0;j<col;j++) { dfs(0,j,board); dfs(row-1,j,board); } for(i=0;i<row;i++) { for(j=0;j<col;j++) { if(board[i][j]==‘O‘) board[i][j]=‘X‘; else if(board[i][j]==‘#‘) board[i][j]=‘O‘; } } } void dfs(int row,int col,vector<vector<char> > &board) { if(row<0||row>=(int)board.size()||col<0||col>=(int)board[0].size()) return; if(board[row][col]!=‘O‘) return; board[row][col]=‘#‘; dfs(row-1,col,board); dfs(row+1,col,board); dfs(row,col-1,board); dfs(row,col+1,board); }};int main(){ Solution s; //vector<vector<char> > vec={{‘X‘,‘X‘,‘X‘,‘X‘},{‘X‘,‘O‘,‘O‘,‘X‘},{‘X‘,‘X‘,‘O‘,‘X‘},{‘X‘,‘O‘,‘X‘,‘X‘}}; vector<vector<char> > vec={{‘O‘,‘O‘,‘O‘,‘O‘},{‘O‘,‘O‘,‘O‘,‘O‘},{‘O‘,‘O‘,‘O‘,‘O‘},{‘O‘,‘O‘,‘O‘,‘O‘}}; s.solve(vec); for(auto a:vec) { for(auto v:a) cout<<v<<" "; cout<<endl; }}
Surrounded Regions
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。