'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
Idea:
Use BFS
class Solution {
public:
void solve(vector<vector<char>> &board) {
int row = board.size();
if (row<=1) return;
int col = board[0].size();
if (col<=1) return;
for (int c=0; c<col; c=c+col-1)
for (int r=0; r<row; r++)
{
if (board[r][c]=='O')
findBdCoords(board,r, c, row, col);
}
for (int r=0; r<row; r=r+row-1)
for (int c=0; c<col; c++)
{
if (board[r][c]=='O')
findBdCoords(board,r, c, row, col);
}
for (int r=0; r<row; r++)
for (int c=0; c<col; c++)
{
if (board[r][c]=='O')
board[r][c]='X';
if (board[r][c]=='B')
board[r][c]='O';
}
}
void findBdCoords(vector<vector<char>> &board, int r, int c, int row, int col)
{
if (board[r][c]!='B')
board[r][c]='B';
queue<pair<int,int>> q;
q.push(make_pair(r,c));
while(!q.empty())
{
//4 directions neighbor
pair<int,int> cur = q.front();
q.pop();
r = cur.first, c = cur.second;
pair<int, int> neis[4]={{r+1,c},{r-1,c},{r,c+1},{r,c-1}};
for (int i=0; i<4; i++)
{
int rt = neis[i].first, ct = neis[i].second;
if (rt>=0&&ct>=0&&rt<row&&ct<col&&board[rt][ct]=='O')
{
q.push(make_pair(rt,ct));
board[rt][ct]='B';
}
}
}
}
};
No comments:
Post a Comment