LeetCode Q130: Surrounded Regions

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

Solutoin:
Region grow, if meet 'O' on boundary, give up filling the region.

	class Solution {
	public:
	void solve(vector<vector<char>>& board) {
	if(board.empty())
	return;
	int rows=board.size();
	int cols=board[0].size();
	int flag[rows*cols]={0};
	bool violate=false;
	for(int i=0; i<rows; i++){
	for(int j=0; j<cols; j++){
	int idx=i*cols+j;
	violate=false;
	if(board[i][j]=='O'&&flag[idx]==0){
	vector<int> H;
	queue<int> myQ;
	myQ.push(idx);
	flag[idx]=1;
	while(!myQ.empty()){
	int c=myQ.front();
	myQ.pop();
	H.push_back(c);
	int r_=c/cols;
	int c_=c%cols;
	if(c_==0||c_==cols-1||r_==0||r_==rows-1)
	violate=true;
	if(r_!=0&&board[r_-1][c_]=='O'){
	int idx_=(r_-1)*cols+c_;
	if(flag[idx_]==0){
	myQ.push(idx_);
	flag[idx_]=1;
	}
	}
	if(r_!=rows-1&&board[r_+1][c_]=='O'){
	int idx_=(r_+1)*cols+c_;
	if(flag[idx_]==0){
	myQ.push(idx_);
	flag[idx_]=1;
	}
	}
	if(c_!=0&&board[r_][c_-1]=='O'){
	int idx_=r_*cols+c_-1;
	if(flag[idx_]==0){
	myQ.push(idx_);
	flag[idx_]=1;
	}
	}
	if(c_!=cols-1&&board[r_][c_+1]=='O'){
	int idx_=r_*cols+c_+1;
	if(flag[idx_]==0){
	myQ.push(idx_);
	flag[idx_]=1;
	}
	}
	}
	if(violate==false){
	for(int i=0; i<H.size(); i++){
	int r_=H[i]/cols;
	int c_=H[i]%cols;
	board[r_][c_]='X';
	}
	}
	}
	else
	continue;
	}
	}
	}
	};

view raw Q130.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	void helper(vector<vector<char>>& board, int r, int c, vector<vector<int>>& mark){
	if(mark[r][c]==1)
	return;
	int pos[]={0, 0, 0, -1, 0, 1, -1, 0, 1, 0};
	queue<pair<int, int> > myQ;
	myQ.push(pair<int, int>(r, c));
	while(!myQ.empty()){
	pair<int, int> front = myQ.front();
	myQ.pop();
	for(int i=0; i<5; i++){
	int row = front.first+pos[2*i];
	int col = front.second+pos[2*i+1];
	if(row>=0&&row<=board.size()-1&&col>=0&&col<=board[0].size()-1&&board[row][col]=='O'&&mark[row][col]==0){
	mark[row][col]=1;
	myQ.push(pair<int, int>(row, col));
	}
	}
	}
	}
	void solve(vector<vector<char>>& board) {
	if(board.empty())
	return;
	vector<vector<int> > mark(board.size(), vector<int>(board[0].size(), 0));
	for(int i=0; i<board.size(); i++)
	for(int j=0; j <board[0].size(); j++)
	if((i==0||j==0||i==board.size()-1||j==board[0].size()-1)&&board[i][j]=='O')
	helper(board, i, j, mark);
	for(int i=0; i<board.size(); i++)
	for(int j=0; j <board[0].size(); j++)
	if(board[i][j]=='O'&&mark[i][j]==0)
	board[i][j]='X';
	}
	};

view raw Q130Rnd2.cpp hosted with ❤ by GitHub