题目:
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
class Solution
{
public:
void solve(vector
> &board)
{
if(board.empty())
{
return;
}
m = board.size();
n = board[0].size();
for(int i=0;i
s_pair; void squein(vector
> &board,int i,int j) { queue
q; vector
result; s_pair start = make_pair(i,j); if(IsBigO(board,i,j)) { board[i][j]='-'; q.push(make_pair(i,j)); } while(!q.empty()) { s_pair num = q.front(); q.pop(); result = onein(board,num.first,num.second); for(int s=0;s < result.size();s++) { q.push(result[s]); } } } bool IsBigO(vector
> &board,int i,int j) { if(i>=m || i<0 || j>=n || j<0 || board[i][j]!='O') { return false; } return true; } vector
onein(vector
> &board,int i,int j) { vector
result; s_pair tem[4]={make_pair(i-1,j),make_pair(i+1,j),make_pair(i,j-1),make_pair(i,j+1)}; for(int para=0;para<4;para++) { if(IsBigO(board,tem[para].first,tem[para].second)) { board[tem[para].first][tem[para].second]='-'; result.push_back(tem[para]); } } return result; } };