130. Surrounded Regions
Total Accepted: 54885
Total Submissions: 336458
Difficulty: Medium
Given a 2D board containing
A region is captured by flipping all
For example,
After running your function, the board should be:
Subscribe to see which companies asked this question
Hide Tags
Breadth-first Search Union Find
Hide Similar Problems
(M) Number of Islands (M) Walls and Gates
分析:
前の問題のおかげで、200.Number of Islands,この問題の構想は比較的明らかである.
次の答えRuntime Error、ネットを調べてみると、スタックが溢れているはずです!
他人のアルゴリズムを学ぶ:
広さ優先アルゴリズム
注:本博文はEbowTangオリジナルで、その後も本論文を更新する可能性があります.転載する場合は、必ずこの情報をコピーしてください!
原文住所:http://blog.csdn.net/ebowtang/article/details/51638278
原作者ブログ:http://blog.csdn.net/ebowtang
このブログLeetCodeの問題解索引:http://blog.csdn.net/ebowtang/article/details/50668895
Total Submissions: 336458
Difficulty: Medium
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
Subscribe to see which companies asked this question
Hide Tags
Breadth-first Search Union Find
Hide Similar Problems
(M) Number of Islands (M) Walls and Gates
分析:
前の問題のおかげで、
次の答えRuntime Error、ネットを調べてみると、スタックが溢れているはずです!
class Solution {
public:
void solve(vector<vector<char>>& board) {
int rows=board.size();
if(rows==0 || rows==1)
return;
int cols=board[0].size();
for(int i=0;i<cols;i++)//
if(board[0][i]=='O')
dfs(board,0,i,rows,cols);
for(int i=0;i<cols;i++)//
if(board[rows-1][i]=='O')
dfs(board,rows-1,i,rows,cols);
for(int i=0;i<rows;i++)//
if(board[i][0]=='O')
dfs(board,i,0,rows,cols);
for(int i=0;i<rows;i++)//
if(board[i][cols-1]=='O')
dfs(board,i,cols-1,rows,cols);
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(board[i][j]=='O')
board[i][j]='X';
if(board[i][j]=='D')
board[i][j]='O';
}
}
}
void dfs(vector<vector<char>>& board,int i,int j,int rows,int cols)
{
board[i][j]='D';// D， O， X
if(i < rows-1 && board[i+1][j] == 'O')//
dfs(board,i+1,j,rows,cols);
if(j < cols-1 && board[i][j+1] == 'O')//
dfs(board,i,j+1,rows,cols);
if(i > 0 && board[i-1][j] == 'O')//
dfs(board,i-1,j,rows,cols);
if(j > 0 && board[i][j-1] == 'O')//zuo
dfs(board,i,j-1,rows,cols);
}
};他人のアルゴリズムを学ぶ:
広さ優先アルゴリズム
/**------------------------------------
* ：2015-02-06
* ：SJF0115
* : 130.Surrounded Regions
* ：https://oj.leetcode.com/problems/surrounded-regions/
* ：AC
* ：LeetCode
* ：
---------------------------------------**/
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Solution {
public:
void solve(vector<vector<char> > &board) {
int row = board.size();
if(row == 0){
return;
}//if
int col = board[0].size();
//
if(row <= 2 || col <= 2){
return;
}//if
//
for(int i = 0;i < col;++i){
//
BFS(board,row,col,0,i);
//
BFS(board,row,col,row-1,i);
}//for
//
for(int j = 0;j < row;++j){
//
BFS(board,row,col,j,0);
//
BFS(board,row,col,j,col-1);
}//for
for(int i = 0;i < row;++i){
for(int j = 0;j < col;j++){
// o
if(board[i][j] == 'O'){
board[i][j] = 'X';
}//if
// o
else if(board[i][j] == '.'){
board[i][j] = 'O';
}
}//for
}//for
}
private:
// row col x ,y board
void BFS(vector<vector<char>> &board,int row,int col,int x,int y){
queue<pair<int,int> > q;
Pass(board,row,col,x,y,q);
while(!q.empty()){
pair<int,int> point = q.front();
q.pop();
x = point.first;
y = point.second;
// left
Pass(board,row,col,x,y+1,q);
// right
Pass(board,row,col,x,y-1,q);
// up
Pass(board,row,col,x-1,y,q);
// down
Pass(board,row,col,x+1,y,q);
}//while
}
//
void Pass(vector<vector<char>> &board,int row,int col,int x,int y,queue<pair<int,int> > &q){
// o
if(x < 0 || x >= row || y < 0 || y >= col || board[x][y] != 'O'){
return;
}//if
// o
board[x][y] = '.';
//
q.push(make_pair(x,y));
}
};
int main(){
Solution s;
/*vector<vector<char> > board = {
{'X','X','X','X'},
{'X','O','O','X'},
{'X','X','O','X'},
{'X','O','X','X'}
};*/
vector<vector<char> > board = {
{'X','X','X'},
{'X','O','X'},
{'X','X','X'}
};
s.solve(board);
//
for(int i = 0;i < board.size();i++){
for(int j = 0;j < board[i].size();j++){
cout<<board[i][j]<<" ";
}//for
cout<<endl;
}//for
return 0;
}注:本博文はEbowTangオリジナルで、その後も本論文を更新する可能性があります.転載する場合は、必ずこの情報をコピーしてください!
原文住所:http://blog.csdn.net/ebowtang/article/details/51638278
原作者ブログ:http://blog.csdn.net/ebowtang
このブログLeetCodeの問題解索引:http://blog.csdn.net/ebowtang/article/details/50668895