题解 | #被围绕的区域#
被围绕的区域
http://www.nowcoder.com/practice/3946670643fe4ec2aedcc2be45aed1a9
描述
给定一个 n*m 大小的的矩阵，矩阵中由 ‘X' 和 'O' 构成，找到所有被 'X' 围绕的区域，并将其用 'X' 填充。
例如：
[['X','X','X','X'],
['X','O','O','X'],
['X','O','X','X'],
['X','X','O','X']]
中间的三个 ‘O’ 被 'X'围绕，因此将其填充为 'X' ，但第四行的 'O' 下方没有被 'X' 围绕，因此不改变，结果为
[['X','X','X','X'],
['X','X','X','X'],
['X','X','X','X'],
['X','X','O','X']]
数据范围： 
，矩阵中保证只含有 'X' 和 'O'
问题分析：首先最外围的状态不受其他位置的影响，所以我们需要做的就是检查中间部分的上，下，左，右
是否有'X'。但凡任何一个方向没有'X'，这个位置就没有被包围。否则就是被围住的。
这个算法是简单粗暴的，有重复操作的过程，但也是最简单的。
时间复杂度O(n2m或nm2)：最坏情况是全为O时，这样里面的元素每个都要查（n+m-2）次，
而需要查的元素总共有n*m-2(m+n-2)个，所以复杂度为n2m或nm2，
空间复杂度O(1)：只定义了几个变量
优化思路：定义一个结构体
struct A {
bool up;//保存当前检查到的上面是否有X，有就为1，否就为0
bool left;//保存当前检查到左边是否有X，有就为1，否就为0；
int low;//下面开始出现x的位置
int right;//右边开始出现x的位置
* };
保存每个位置的左边是否出现x，上边是否出现x，因为整个遍历过程是从左向右，从上到下的，在定义一个vector<A> 型的数组，保存每次遍历结果，
这样当出现遍历到(i,j)位置只需要检查上一个是否为X,是x直接不用管，否则直接看上一个的up。同理检查左边，左边第一个是X，直接不用管，
否则看左边第一个的left值。而右边只需要看左边第一个的right是否大于当前j。同样的下边看上一个的low是否大于当前的i。
如果想进一步优化，还可以定义两个bool型数组，col[m]和row[n]。row[i]只要该行全为O，就为true，col[j]只要该列全为O就为true，
这样每次先判断row[i]和col[j] 是否为真，真直接为O。这样即使是最坏情况时间复杂度也只有O(n*m)。但就是空间复杂度高了点，对n和m比较大
还是可以用空间换时间的。
上面两个优化思路就不写了，这题目n和m也不是特别大。
class Solution {
public:
vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
int n=board.size();
if(n==1) return board;//只有一行直接返回
int m=board[0].size();
if(m==1) return board;//只有一列直接返回
for(int i=1;i<n-1;++i)
for(int j=1;j<m-1;++j)
if(board[i][j]=='O'){
//结果返回4，说明上下左右都有X，赋值为X，否则不做操作
if(check(board,i,j,n-1,m-1)==4)
board[i][j]='X';
}
return board;
}
int check(vector<vector<char> > &board,int i,int j,int n,int m) {
int num=0;
for(int k=i-1;k>=0;--k) //检查(i,j)上面
if(board[k][j]=='X') {++num;break;}
for(int k=i+1;k<=n;++k)//检查(i,j)下面
if(board[k][j]=='X') {++num;break;}
for(int k=j-1;k>=0;--k)//检查(i,j)左边
if(board[i][k]=='X') {++num;break;}
for(int k=j+1;k<=m;++k)//检查(i,j)右边
if(board[i][k]=='X') {++num;break;}
return num;
}
};
拼多多集团-PDD工作强度 281人发布
