Problem Statement (link):
Given a 2D board containing
A region is captured by flipping all
For example,
'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
Analysis:
Rather than recording the 2D positions for any scanned 'O', a trick is to substitute any border 'O's with another character - here in the Code I use 'Y'. And scan the board again to change any rest 'O's to 'X's, and change 'Y's back to 'O's.
We start searching 'O' from the four borders. I tried DFS first, the OJ gives Runtime error on the 250x250 large board; In the Sol 2 below, I implement BFS instead, and passed all tests.
The time complexity is O(n^2), as in the worst case, we may need to scan the entire board.
Code:
1, DFS
class Solution {
public:
// dfs - Runtime error on large board 250x250
void dfs(vector<vector<char>> &board, int r, int c) {
if (r<||r>board.size()-||c<||c>board[].size()-||board[r][c]!='O')
return;
board[r][c]='Y';
dfs(board, r-, c);
dfs(board, r+, c);
dfs(board, r, c-);
dfs(board, r, c+);
}
void solve(vector<vector<char>> &board) {
if (board.empty() || board.size()< || board[].size()<)
return;
int r=board.size();
int c=board[].size();
// dfs from boundary to inside
for (int i=; i<c; i++) {
if (board[][i]=='O')
dfs(board, , i); // first row
if (board[c-][i]=='O')
dfs(board, c-, i); // last row
}
for (int i=; i<board.size(); i++) {
if (board[i][]=='O')
dfs(board, i, ); // first col
if (board[i][c-])
dfs(board, i, c-); // last col
}
// scan entire matrix and set values
for (int i=; i<board.size(); i++) {
for (int j=; j<board[].size(); j++) {
if (board[i][j]=='O')
board[i][j]='X';
else if (board[i][j]=='Y')
board[i][j]='O';
}
}
}
};
2, BFS
class Solution {
public:
void solve(vector<vector<char>> &board) {
if (board.empty() || board.size()< || board[].size()<)
return;
int r=board.size();
int c=board[].size();
// queues to store row and col indices
queue<int> qr;
queue<int> qc;
// start from boundary
for (int i=; i<c; i++) {
if (board[][i]=='O') { qr.push(); qc.push(i); }
if (board[r-][i]=='O') { qr.push(r-); qc.push(i); }
}
for (int i=; i<r; i++) {
if (board[i][]=='O') { qr.push(i); qc.push(); }
if (board[i][c-]=='O') { qr.push(i); qc.push(c-); }
}
// BFS
while (!qr.empty()) {
int rt=qr.front(); qr.pop();
int ct=qc.front(); qc.pop();
board[rt][ct]='Y';
if (rt->= && board[rt-][ct]=='O') { qr.push(rt-); qc.push(ct); } //go up
if (rt+<r && board[rt+][ct]=='O') { qr.push(rt+); qc.push(ct); } // go down
if (ct->= && board[rt][ct-]=='O') { qr.push(rt); qc.push(ct-); } // go left
if (ct+<c && board[rt][ct+]=='O') { qr.push(rt); qc.push(ct+); } // go right
}
// scan entire matrix and set values
for (int i=; i<board.size(); i++) {
for (int j=; j<board[].size(); j++) {
if (board[i][j]=='O') board[i][j]='X';
else if (board[i][j]=='Y') board[i][j]='O';
}
}
}
};
http://justcodings.blogspot.com/2014/07/leetcode-surrounded-regions.html