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 {
struct position
{
int x, y;
position(int a, int b): x(a), y(b) {}
};
public:
void solve(vector<vector<char>>& board) {
int row = board.size();
if(row <= )
return;
int col = board[].size();
if(col <= )
return;
queue<position> q;
int i, j;
for(i = ; i < col; i++)
{
if('O' == board[][i])
q.push(position(, i));
if('O' == board[row-][i])
q.push(position(row-, i));
}
for(i = ; i < row; i++)
{
if('O' == board[i][])
q.push(position(i, ));
if('O' == board[i][col-])
q.push(position(i, col-));
}
while(!q.empty())
{
position p = q.front();
q.pop();
board[p.x][p.y] = 'N';
if(p.x > && 'O' == board[(p.x)-][p.y])
q.push(position((p.x)-, p.y));
if(p.x < row- && 'O' == board[(p.x)+][p.y])
q.push(position((p.x)+, p.y));
if(p.y > && 'O' == board[p.x][(p.y)-])
q.push(position(p.x, (p.y)-));
if(p.y < col- && 'O' == board[p.x][(p.y)+])
q.push(position(p.x, (p.y)+));
}
for(i = ; i < row; i++)
{
for(j = ; j < col; j++)
{
if('O' == board[i][j])
board[i][j] = 'X';
if('N' == board[i][j])
board[i][j] = 'O';
}
cout<<endl;
}
}
};
先找到四条边缘上面的字符，再找和这些字符相邻的字符。