现在有一个仅包含‘X’和‘O’的二维板，请捕获所有的被‘X’包围的区域
捕获一个被包围区域的方法是将被包围区域中的所有‘O’变成‘X’
例如
X X X X X O O X X X O X O X X X执行完你给出的函数以后，这个二维板应该变成：
X X X X X X X X X X X X O X X X
[编程题]包围区域
/*
* 所有与四条边相连的O都保留，其他O都变为X
* 遍历四条边上的O，并深度遍历与其相连的O，将这些O都转为*
* 将剩余的O变为X
* 将剩余的*变为O
*/
public int rowNum = 0;
public int colNum = 0;
public void solve(char[][] board) {
if(board == null || board.length <= 0|| board[0].length <= 0){
return;
}
rowNum = board.length;
colNum = board[0].length;
for(int i = 0; i < colNum; i++){
dfs(board, 0, i);
dfs(board, rowNum-1, i);
}
for(int i = 0; i < rowNum; i++){
dfs(board, i, 0);
dfs(board, i, colNum-1);
}
for(int i = 0; i < rowNum; i++){
for(int j = 0; j < colNum; j++){
if(board[i][j] == 'O'){
board[i][j] = 'X';
}
}
}
for(int i = 0; i < rowNum; i++){
for(int j = 0; j < colNum; j++){
if(board[i][j] == '*'){
board[i][j] = 'O';
}
}
}
}
private void dfs(char[][] board, int row, int col) {
// TODO Auto-generated method stub
if(board[row][col] == 'O'){
board[row][col] = '*';
if(row > 1){
dfs(board, row-1, col);
}
if(col > 1){
dfs(board, row, col-1);
}
if(row < rowNum-1){
dfs(board, row+1, col);
}
if(col < colNum-1){
dfs(board, row, col+1);
}
}
}
编辑于 2016-07-09 10:18:49
回复(16)
//找那些在边界上的O,这些O一定不能转换为X，而且与这些O相连的在内部的O也不能转换为x
//感谢一楼，渣渣我就是抄的一楼的。。。。
//方法：1.暂时修改那些在边界且与边界相连（深搜找这些点）的点值为*
//2.接着修改剩余的值为O的点为X，这些就是surrounded by x的点了
//3.接着将值为*的点复原为O
public class Solution {
public void solve(char[][] board) {
if(board==null||board.length<3||board[0].length<3){
return ;
}
int row=board.length;
int col=board[0].length;
for(int i=0;i<row;++i){
dfs(board,i,0);//上边界
dfs(board,i,col-1);//下边界
}
for(int i=0;i<col;++i){
dfs(board,0,i);//左边界
dfs(board,row-1,i);//右边界
}
for(int i=0;i<row;++i){
for(int j=0;j<col;++j){
if(board[i][j]=='O'){
board[i][j]='X';
}
if(board[i][j]=='*'){
board[i][j]='O';
}
}
}
}
public void dfs(char[][]board,int i,int j){
if(i<0||j<0||i>=board.length||j>=board[0].length){
return ;
}
if(board[i][j]!='O'){
return ;
}
board[i][j]='*';
dfs(board,i-1,j);
dfs(board,i+1,j);
dfs(board,i,j-1);
dfs(board,i,j+1);
}
}
//感谢一楼，渣渣我就是抄的一楼的。。。。
//方法：1.暂时修改那些在边界且与边界相连（深搜找这些点）的点值为*
//2.接着修改剩余的值为O的点为X，这些就是surrounded by x的点了
//3.接着将值为*的点复原为O
public class Solution {
public void solve(char[][] board) {
if(board==null||board.length<3||board[0].length<3){
return ;
}
int row=board.length;
int col=board[0].length;
for(int i=0;i<row;++i){
dfs(board,i,0);//上边界
dfs(board,i,col-1);//下边界
}
for(int i=0;i<col;++i){
dfs(board,0,i);//左边界
dfs(board,row-1,i);//右边界
}
for(int i=0;i<row;++i){
for(int j=0;j<col;++j){
if(board[i][j]=='O'){
board[i][j]='X';
}
if(board[i][j]=='*'){
board[i][j]='O';
}
}
}
}
public void dfs(char[][]board,int i,int j){
if(i<0||j<0||i>=board.length||j>=board[0].length){
return ;
}
if(board[i][j]!='O'){
return ;
}
board[i][j]='*';
dfs(board,i-1,j);
dfs(board,i+1,j);
dfs(board,i,j-1);
dfs(board,i,j+1);
}
}
发表于 2017-12-15 19:57:14
回复(1)
也是一楼的思路
从四周的'O'开始深度优先搜索 将其标记为'a'
然后将剩下的'O'变成X
最后将'a'变回'O'
class Solution {
public:
void dfs(vector<vector<char>> &board, int row, int col,
int x, int y){
int stepx[4] = {1, -1, 0, 0}; //用数组保存路径
int stepy[4] = {0, 0, 1, -1}; //吐槽一下C++这种在类里面的题目没法用全局变量
if(board[x][y] == 'O'){
board[x][y] = 'a';
for(int i = 0; i < 4; i++){ //上下左右四个方向搜索
if(x + stepx[i] >= 0 && x + stepx[i] < row &&
y + stepy[i] >= 0 && y + stepy[i] < col &&
board[x + stepx[i]][y + stepy[i]] == 'O'){
dfs(board, row, col, x + stepx[i], y + stepy[i]);
}
}
}
}
void solve(vector<vector<char>> &board) {
int row = board.size(); if(row == 0) return; //防止出很贱的测试样例
int col = board[0].size();
for(int i = 0; i < col; i++) dfs(board, row, col, 0, i); //第一行
for(int i = 0; i < col; i++) dfs(board, row, col, row - 1, i); //最后一行
for(int i = 0; i < row; i++) dfs(board, row, col, i, 0); //第一列
for(int i = 0; i < row; i++) dfs(board, row, col, i, col - 1); //最后一列
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++){
if(board[i][j] == 'O') board[i][j] = 'X';
if(board[i][j] == 'a') board[i][j] = 'O';
}
}
};
发表于 2019-04-23 22:19:37
回复(0)
//感谢一楼的思路，自己再理解一下，就是O能找到出口的问题，然后从出口处的O反过来去找
//出来的路径。
public class Solution {
public void DFS(char[][] board, int row, int col)
{
if(row < 0 || row>(board.length - 1) || col < 0 || col >(board[0].length -1) ) return ;
if(board[row][col] == 'O')
{
board[row][col] = '*';
DFS(board, row-1,col);
DFS(board,row+1,col);
DFS(board,row,col-1);
DFS(board,row,col+1);
}
}
public void solve(char[][] board) {
if(board.length <= 0) return;
int row = board.length;
int col = board[0].length;
for(int i = 0 ; i != row ; i++) {
DFS(board,i,col-1);
DFS(board,i,0);
}
for(int i = 0 ; i != col ;i++)
{
DFS(board,0,i);
DFS(board,row-1,i);
}
for(int i = 0 ; i != row ; i++)
for(int j = 0 ; j != col ; j++)
{ if(board[i][j] == 'O') board[i][j] = 'X';
if(board[i][j] == '*') board[i][j] = 'O';
}
}
}
编辑于 2017-11-09 12:04:38
回复(5)
public class Solution {
public void solve(char[][] board) {
if(board.length == 0) return;
int[][] direction = {{1, 0}, { - 1, 0}, {0, 1}, {0, - 1}};
// 第一行
for (int i = 0; i < board[0].length; i ++ ) {
if(board[0][i] == 'O') {
board[0][i] = '*';
dfs(board, 0, i, direction);
}
}
// 最后一行
for (int i = 0; i < board[0].length; i ++ ) {
if(board[board.length - 1][i] == 'O') {
board[board.length - 1][i] = '*';
dfs(board, board.length - 1, i, direction);
}
}
// 第一列
for (int i = 0; i < board.length; i ++ ) {
if(board[i][0] == 'O') {
board[i][0] = '*';
dfs(board, i, 0, direction);
}
}
// 最后一列
for (int i = 0; i < board.length; i ++ ) {
if(board[i][board[0].length - 1] == 'O') {
board[i][board[0].length - 1] = '*';
dfs(board, i, board[0].length - 1, direction);
}
}
// *变O,O变X
for (int i = 0; i < board.length; i ++ ) {
for (int j = 0; j < board[0].length; j ++ ) {
if(board[i][j] == 'O') board[i][j] = 'X';
else if(board[i][j] == '*') board[i][j] = 'O';
}
}
}
public static void dfs(char[][] board, int x, int y, int[][] direction) {
for (int i = 0; i < direction.length; i ++ ) {
int nx = x + direction[i][0];
int ny = y + direction[i][1];
if(nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length && board[nx][ny] == 'O') {
board[nx][ny] = '*';
dfs(board, nx, ny, direction);
}
}
}
}
编辑于 2016-11-01 16:22:44
回复(0)
//其实不难嘛
//从靠边的O出发 找所有临接的O设为不可变I 其他的O都可变
public class Solution {
public void solve(char[][] board) {
if(board.length==0){
return;
}
if(board[0].length==0){
return;
}
int length=board.length;
int width=board[0].length;
for(int i=0;i<length;i++){
searchAllImutable(board , i, 0);
}
for(int i=0;i<length;i++){
searchAllImutable(board , i, width-1);
}
for(int i=0;i<width;i++){
searchAllImutable(board , 0, i);
}
for(int i=0;i<width;i++){
searchAllImutable(board , length-1, i);
}
for(int i=0;i<length;i++){
for(int j=0;j<width;j++){
if(board[i][j]=='O'){
board[i][j]='X';
}
if(board[i][j]=='I'){
board[i][j]='O';
}
}
}
return;
}
public void searchAllImutable(char[][] board, int x, int y) {
if(x<0 || y<0){
return;
}
if(x>=board.length || y>=board[0].length){
return;
}
if(board[x][y]=='X'){
return;
}
if(board[x][y]=='I'){
return;
}
if(board[x][y]=='O'){
board[x][y]='I';
searchAllImutable(board , x+1, y);
searchAllImutable(board , x-1, y);
searchAllImutable(board , x, y+1);
searchAllImutable(board , x, y-1);
}
}
}
发表于 2017-08-06 16:21:54
回复(1)
class Solution {
public:
void solve(vector<vector<char>> &board) {
if (board.empty()) return;
const int m = board.size(), n = board[0].size();
for (int x = 0; x < n; ++x) DFS(board, m, n, x, 0), DFS(board, m, n, x, m - 1);
for (int y = 0; y < m; ++y) DFS(board, m, n, 0, y), DFS(board, m, n, n - 1, y);
unordered_map<char, char> mp{{'#', 'O'}, {'O', 'X'}, {'X', 'X'}};
for (int y = 0; y < m; ++y)
for (int x = 0; x < n; ++x)
board[y][x] = mp[board[y][x]];
}
private:
void DFS(vector<vector<char>>& board, int m, int n, int x, int y) {
if (x < 0 || x == n || y < 0 || y == m || board[y][x] != 'O')
return;
board[y][x] = '#';
DFS(board, m, n, x - 1, y);
DFS(board, m, n, x + 1, y);
DFS(board, m, n, x, y - 1);
DFS(board, m, n, x, y + 1);
}
};
发表于 2021-07-31 10:51:21
回复(0)
public class Solution {
public void solve(char[][] board) {
/**
* 由题目可以知道，只要与边界上"O"连通的"O"都不能被替换
* 反之，我们可以遍历边界上的"O"，从每一个边界的"O"开始
* 递归遍历与其连通的"O"，并标记出来
* 最后把标记的"O"保留，未标记的"O"替换为"X"
* 一共遍历两次，时间复杂度O(n)，未使用额外存储空间
* 容易出错的地方，数组下标和二维空间坐标正好是反过来的，注意转化
* 另外数组不一定是正方形，长和宽不一定相等
**/
if(board.length < 1) return;
int m = board.length;
int n = board[0].length;
// 只有边缘元素不需要处理
if(n<3||m<3){
return;
}
// 遍历上边缘
for(int i=0,j=0; j<n; j++){
if(board[i][j]=='O'){
spread(board, i, j);
}
}
// 遍历右边缘
for(int j=n-1,i=0; i<m; i++){
if(board[i][j]=='O'){
spread(board, i, j);
}
}
// 遍历下边缘
for(int j=n-1,i=m-1; j>=0; j--){
if(board[i][j]=='O'){
spread(board, i, j);
}
}
// 遍历左边缘
for(int j=0,i=m-1; i>=0; i--){
if(board[i][j]=='O'){
spread(board, i, j);
}
}
// 替换'A'和'O'
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(board[i][j]=='O'){
board[i][j]='X';
}
if(board[i][j]=='A'){
board[i][j]='O';
}
}
}
}
public static void spread(char[][] board, int x, int y){
int m = board.length;
int n = board[0].length;
// 标记
board[x][y] = 'A';
if(x-1>=0&&board[x-1][y]=='O'){
spread(board, x-1, y);
}
if(x+1<m&&board[x+1][y]=='O'){
spread(board, x+1, y);
}
if(y-1>=0&&board[x][y-1]=='O'){
spread(board, x, y-1);
}
if(y+1<n&&board[x][y+1]=='O'){
spread(board, x, y+1);
}
}
}
发表于 2020-01-04 12:26:36
回复(0)
class Solution {
public:
void infect(vector<vector<char>>&board,int row,int col,char identify,char target){
if(row<0||row>=board.size()||col<0||col>=board[0].size()||board[row][col]!=identify)return;
board[row][col]=target;
infect(board,row+1,col,identify,target);
infect(board,row,col+1,identify,target);
infect(board,row,col-1,identify,target);
infect(board,row-1,col,identify,target);
}
void boarderChange(vector<vector<char>>&board,char identify,char target){
for(int i=0;i<board.size();i++){
infect(board,i,0,identify,target);
infect(board,i,board[0].size()-1,identify,target);
}
for(int i=0;i<board[0].size();i++){
infect(board,0,i,identify,target);
infect(board,board.size()-1,i,identify,target);
}
}
void solve(vector<vector<char>> &board) {
//先从边界走起,为O的圈改为1,然后遍历整个表,为圈的感染一块全变为x,最后将1还原为O
//看起来复杂度高,实际复杂度是O(n)的
if(board.empty())return;
boarderChange(board,'O','1');
//---------------------------------------
for(int i=1;i<board.size()-1;i++)
for(int j=1;j<board[0].size()-1;j++)
infect(board,i,j,'O','X');
boarderChange(board,'1','O');
}
};
发表于 2019-08-17 18:29:22
回复(0)
从不可能被包围的圆圈突破，献上比较简短的代码
class Solution {
public:
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void dfs(int x,int y,vector<vector<char>> &board){
int m = board[0].size();
int n = board.size();
if(board[x][y]!='O') return;
board[x][y]='B';
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny = y+dy[i];
if(nx>=0&&nx<n&&ny>=0&&ny<m){
dfs(nx,ny,board);
}
}
}
void solve(vector<vector<char>> &board) {
if(board.size()==0) return;
int m = board[0].size();
int n = board.size();
// cout<<n<<' '<<m<<endl;
for(int i=0;i<n;i++){
dfs(i,0,board);
dfs(i,m-1,board);
}
for(int j=0;j<m;j++){
dfs(0,j,board);
dfs(n-1,j,board);
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(board[i][j]=='O')
board[i][j]='X';
else if(board[i][j]=='B')
board[i][j]='O';
}
}
}
};
发表于 2019-04-11 01:01:57
回复(0)
/**
* 1.矩阵四边的O皆不符合条件，所以我们把O以及与O连接的点标记为* 2.接着修改剩余的O值为X 3.将没有被包围的点（*）恢复为O
*/
public class Solution {
public void solve(char[][] board) {
if (board == null || board.length < 3 || board[0].length < 3) {
return;
}
int rows = board.length;
int cols = board[0].length;
for (int i = 0; i < rows; i++) {
dfs(board, i, rows, 0, cols); // 左边界
dfs(board, i, rows, cols - 1, cols); // 右边界
}
for (int j = 0; j < cols; j++) {
dfs(board, 0, rows, j, cols); // 上边界
dfs(board, rows - 1, rows, j, cols); // 下边界
}
for(int i = 0; i < rows ; i++){
for(int j = 0; j < cols; j++){
if(board[i][j] == 'O'){
board[i][j] = 'X';
}else if(board[i][j] == '*'){
board[i][j] = 'O';
}
}
}
}
public void dfs(char[][] board, int row, int rows, int col, int cols) {
if (row < 0 || row >= rows || col < 0 || col >= cols) {
return;
}
if (board[row][col] == 'O') {
board[row][col] = '*';
dfs(board, row + 1, rows, col, cols);
dfs(board, row - 1, rows, col, cols);
dfs(board, row, rows, col + 1, cols);
dfs(board, row, rows, col - 1, cols);
}
}
}
发表于 2018-09-09 09:42:48
回复(0)
public void solve(char[][] board) {
if (board == null || board.length == 0) {
// print(board);
return;
}
//上边
for (int i = 0; i < board[0].length; i++) {
if (board[0][i] == 'O') {
board[0][i] = '*';
if (board.length != 1) {
dfs(board, 1, i);
}
}
}
//右边
for (int i = 0; i < board.length; i++) {
if (board[i][board[0].length - 1] == 'O') {
board[i][board[0].length - 1] = '*';
if (board.length != 1) {
dfs(board, i, board[0].length - 2);
}
}
}
//下面
for (int i = 0; i < board[0].length; i++) {
if (board[board.length - 1][i] == 'O') {
board[board.length - 1][i] = '*';
if (board.length != 1) {
dfs(board, board.length - 2, i);
}
}
}
//左边
for (int i = 0; i < board.length; i++) {
if (board[i][0] == 'O') {
board[i][0] = '*';
if (board.length != 1) {
dfs(board, i, 1);
}
}
}
clean(board);
// print(board);
}
private void clean(char[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '*') {
board[i][j] = 'O';
}
}
}
}
private void dfs(char[][] board, int row, int col) {
if (board[row][col] == 'O') {
board[row][col] = '*';
if (col != 0) {
dfs(board, row, col - 1);
}
if (col != board[0].length - 1) {
dfs(board, row, col + 1);
}
if (row != 0) {
dfs(board, row - 1, col);
}
if (row != board.length - 1) {
dfs(board, row + 1, col);
}
}
}
发表于 2018-07-30 22:03:01
回复(0)
class Solution {
public:
void solve(vector<vector<char>> &board) {
if(board.size()<=0 || board[0].size()<=0) return ;
int row=board.size(),col=board[0].size();
vector<vector<bool> >dp(row,vector<bool>(col,false));
stack<vector<int> >S;
vector<int> tmp(2,0);
for(int i=0;i<row;++i){
for(int j=0;j<col;++j){
if((i==0 || i==row-1 || j==0 ||j==col-1) && board[i][j]=='O' && dp[i][j]==false){
dp[i][j]=true;
tmp[0]=i;
tmp[1]=j;
S.push(tmp);
while(!S.empty()){
int m=S.top()[0],n=S.top()[1];
if(m-1>=0 && dp[m-1][n]==false && board[m-1][n]=='O'){
dp[m-1][n]=true;
tmp[0]=m-1;
tmp[1]=n;
S.push(tmp);
}
if(m+1<row && dp[m+1][n]==false && board[m+1][n]=='O'){
dp[m+1][n]=true;
tmp[0]=m+1;
tmp[1]=n;
S.push(tmp);
}
if(n-1>0 && dp[m][n-1]==false && board[m][n-1]=='O'){
dp[m][n-1]=true;
tmp[0]=m;
tmp[1]=n-1;
S.push(tmp);
}
if(n+1<col && dp[m][n+1]==false && board[m][n+1]=='O'){
dp[m][n+1]=true;
tmp[0]=m;
tmp[1]=n+1;
S.push(tmp);
}
m=S.top()[0],n=S.top()[1];
if(!(m-1>=0 && dp[m-1][n]==false && board[m-1][n]=='O' || m+1<row && dp[m+1][n]==false && board[m+1][n]=='O' || n-1>0 && dp[m][n-1]==false
&& board[m][n-1]=='O' || n+1<col && dp[m][n+1]==false && board[m][n+1]=='O'))
S.pop();
}
}
}
}
for(int i=1;i<row-1;++i){
for(int j=1;j<col-1;++j){
if(board[i][j]=='X' || dp[i][j]==false) board[i][j]='X';
else board[i][j]='O';
}
}
}
};
发表于 2018-06-28 10:03:44
回复(0)
class Solution {
int book[200][200],n,m,next[4][2]={1,0,-1,0,0,1,0,-1};
public:
void solve(vector<vector<char>> &board) {
n=board.size();
if(n==0) return;
m=board[0].size();
int i,j;
memset(book,0,sizeof(book));
for(i=1;i<n-1;i++)
dfs(i,0,board,'+'),dfs(i,m-1,board,'+');
for(j=0;j<m;j++) dfs(0,j,board,'+'),dfs(n-1,j,board,'+');
memset(book,0,sizeof(book));
for(i=0;i<n;i++)
for(j=0;j<m;j++)
dfs(i,j,board,'X');
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(board[i][j]=='+') board[i][j]='O';
}
void dfs(int x,int y,vector<vector<char>> &board,char isp){
if(x<0||x>=n||y<0||y>=m) return;
if(board[x][y]!='O') return;
if(book[x][y]) return;
book[x][y]=1,board[x][y]=isp;
for(int i=0;i<4;i++)
dfs(x+next[i][0],y+next[i][1],board,isp);
}
};
发表于 2018-05-27 13:26:49
回复(0)
利用DFS就可以了：
类似于找岛屿问题，只是对于在边缘的要单独拿出来，并且保存合适的结果。然后再进行转换，思路是比较简单的
class Solution {
public:void DFS(int i, int j, vector<vector<char>> &board, vector<vector<int>> &visit, vector<int> &index, bool &flags) {
visit[i][j] = 1;
index.push_back(i);
index.push_back(j);
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
for (int k = 0; k<4; ++k) {
int new_x = i + dx[k];
int new_y = j + dy[k];
if (new_x >= 0 && new_x<board.size() && new_y >= 0 && new_y<board[0].size() && visit[new_x][new_y] == 0 && board[new_x][new_y] == 'O')
{
if (new_x == 0 || new_x == board.size() - 1 || new_y == 0 || new_y == board[0].size() - 1)
flags = false;
DFS(new_x, new_y, board, visit, index, flags);
}
}
}
void solve(vector<vector<char>> &board) {
if (!board.empty()) {
bool flags = true;
vector<int> index;
vector<vector<int>> visit(board.size(), vector<int>(board[0].size(), 0));
for (int i = 1; i<board.size() - 1; ++i) {
for (int j = 1; j<board[0].size() - 1; ++j) {
if (visit[i][j] == 0 && board[i][j] == 'O')
DFS(i, j, board, visit, index, flags);
if (!index.empty() && flags) {
for (int k = 0; k<index.size() - 1; k=k+2) {
board[index[k]][index[k + 1]] = 'X';
}
}
index.clear();
flags = true;
}
}
}
}
};
发表于 2018-05-07 10:52:04
回复(0)
思路：首先将边界上的O以及与边界O相连的O都标记为N，
然后将其他的O都变为X，最后将N重新变为O即可
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
int row = board.length;
int column = board[0].length;
for (int i = 0; i < row; i++) {
dfs(board, i, 0);
dfs(board, i, column - 1);
}
for (int i = 0; i < column; i++) {
dfs(board, 0, i);
dfs(board, row - 1, i);
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if(board[i][j]=='O'){
board[i][j]='X';
}
if(board[i][j]=='N'){//把标记为N的重新变为O
board[i][j]='O';
}
}
}
}
// 将边界上的O变为N，与边界O相连的所有O都变为N,N是一个标记表示不可变的O
private void dfs(char[][] board, int i, int j) {
int row = board.length;
int column = board[0].length;
if (i < 0 || i >= row || j < 0 || j >= column) {
return;
}
if (board[i][j] == 'X') {
return;
}
if (board[i][j] == 'O') {
board[i][j] = 'N';
dfs(board, i + 1, j);
dfs(board, i - 1, j);
dfs(board, i, j + 1);
dfs(board, i, j - 1);
}
}
编辑于 2018-05-04 15:33:32
回复(0)
class Solution {
public:
void solve(vector<vector<char>> &board) {
if(board.empty())
return;
int rows = board.size();
int cols = board[0].size();
if(rows==0 || cols==0)
return;
for(int j=0;j<cols;j++)
{
DFS(board, 0, j);
DFS(board, rows-1, j); } for(int i=0;i<rows;i++) { DFS(board, i, 0); DFS(board, i, cols-1); } for(int i=0;i<rows;i++) for(int j=0;j<cols;j++) if(board[i][j] == 'O') board[i][j] = 'X'; for(int i=0;i<rows;i++) for(int j=0;j<cols;j++) if(board[i][j] == '*') board[i][j] = 'O';
}
void DFS(vector<vector<char> > &board, int r, int c)
{
if(board[r][c] == 'O')
{
board[r][c] = '*'; int rows = board.size(); int cols = board[0].size(); if(r > 1) DFS(board, r-1, c); if(r < rows-2) DFS(board, r+1, c); if(c > 1) DFS(board, r, c-1); if(c < cols-2) DFS(board, r, c+1); } }
};
发表于 2017-10-04 02:37:15
回复(0)
import java.util.Arrays;
/**
* 感谢赞第一的同学提供思想，从四边开始搜索，把能和4条边上的O连接的点标记出来，
* 最后把标记的点改成‘O',其余点改成'X'
*/
public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}
//行的元素数量
int rowLen = board.length;
//列的元素数量
int colLen = board[0].length;
boolean[][] index = new boolean[rowLen][colLen];
//第一列
for (int i = 0; i < rowLen; i++) {
search(board, index, i, 0);
}
//最后一列
for (int i = 0; i < rowLen; i++) {
search(board, index, i, colLen - 1);
}
//第一行
for (int i = 0; i < colLen; i++) {
search(board, index, 0, i);
}
//最后一行
for (int i = 0; i < colLen; i++) {
search(board, index, rowLen - 1, i);
}
for (int i = 0; i < rowLen; i++) {
for (int j = 0; j < colLen; j++) {
board[i][j] = (board[i][j] == '*' ? 'O' : 'X');
}
}
}
private void search(char[][] board, boolean[][] index, int x,
int y) {
if (x < 0 || y < 0 || x >= board.length || y
>= board[0].length) {
return;
}
if (index[x][y] || board[x][y] == 'X') {
index[x][y] = true;
return;
}
//如果找到了O, 把O改为*
index[x][y] = true;
board[x][y] = '*';
//上下左右都搜索一遍
search(board, index, x - 1, y);
search(board, index, x + 1, y);
search(board, index, x, y - 1);
search(board, index, x, y + 1);
}
}
发表于 2017-06-19 14:38:13
回复(3)
//从四条边开始搜索，遇到“O”就在满足边界条件下进行深度搜索，递归调用搜索函数
#include<vector>
#include<iostream>
using namespace std;
const int CONST_COL = 5;
class surrounded_regions {
public:
void solve(vector<vector<char>> &board) {
int row = board.size();
int col = board[0].size();
if(row <= 2 || col <= 2) return;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if((board[i][j] == 'O' && i == 0) || (board[i][j] == 'O' && i == row - 1))
dfs(board, i, j);
else if((board[i][j] == 'O' && j == 0) || (board[i][j] == 'O' && j == col - 1))
dfs(board, i, j);
}
}
getResult(board);
}
private:
void dfs(vector<vector<char>> &board, int Row, int Col){
if(board[Row][Col] == 'O'){
board[Row][Col] = '*';
if(Row - 1 >= 0)
dfs(board, Row - 1, Col);
if(Row + 1 <= board.size()-1)
dfs(board, Row + 1, Col);
if(Col - 1 >= 0)
dfs(board, Row, Col - 1);
if(Col + 1 < board[0].size())
dfs(board, Row, Col + 1);
}
else
return;
}
void getResult(vector<vector<char>> &board){
for(int row = 0; row < board.size(); row++)
for(int col = 0; col < board[0].size(); col++){
if(board[row][col] == '*')
board[row][col] = 'O';
else if(board[row][col] == 'O')
board[row][col] = 'X';
}
}
};
int main()
{
char arr[][CONST_COL] = {'O','X','X','O','X',
'X','O','O','X','O',
'X','O','X','O','X',
'O','X','O','O','O',
'X','X','O','X','O'};
vector<vector<char>> board;
for(int i = 0; i < CONST_COL; i++){
vector<char> tempArr;
for(int j = 0; j < CONST_COL; j++){
tempArr.push_back(arr[i][j]);
}
board.push_back(tempArr);
}
surrounded_regions SR;
SR.solve(board);
for(auto ivec = board.cbegin(); ivec != board.cend(); ivec++){
for(auto jvec = ivec->cbegin(); jvec != ivec->cend(); jvec++){
cout << *jvec << " ";
}
cout << endl;
}
system("pause");
return 0;
}
发表于 2016-09-04 20:18:45
回复(0)
思路1：看了各位大神的思路都是从四周‘O’入手深度搜索，
搜到的‘O’标记为‘*’，然后剩下的‘O’都是被包围的，
置为‘X’。
思路2：我是遍历每一个点，当遍历到‘O’的时候，进行深搜，
看能不能找到边界，如果可以表示该位置没有被包围，
否则，被包围，置为‘X’。
下面是代码，错误提示：存在数组越界非法访问等情况。
那个大神给瞅一眼，咋就非法访问了呢？ public class Solution {
public static void solve(char[][] board){
if (board == null || board.length <= 2 || board[0].length <= 2)
return;
int x = board.length;
int y = board[0].length;
for(int i=0;i<x;i++){
for(int j=0;j<y;j++){
if(board[i][j] == 'O'){
if(dfs(board, i, j)){
board[i][j] = 'X';
}
}
}
}
}
public static boolean dfs(char[][] board, int x, int y){
int lenx = board.length;
int leny = board[0].length;
int[][] d = {{0,1},{1,0},{0,-1},{-1,0}};
for(int i=0;i<4;i++){
int newx = x+d[i][0];
int newy = y+d[i][1];
if((newx >=0 && newx < lenx)
&& (newy >= 0 && newy < leny)){
if(board[newx][newy] == 'O'){
board[newx][newy] = '*';
if(dfs(board, newx, newy) == false){
board[newx][newy] = 'O';
return false;
}
board[newx][newy] = 'O';
}
}else
return false;
}
return true;
}
}
编辑于 2016-08-09 21:24:39
回复(4)
问题信息
难度：
94条回答
144收藏
25762浏览
通过挑战的用户
查看代码-
2023-02-16 20:04:48
-
2023-02-14 17:54:04 -
2022-09-13 11:50:57 -
2022-09-04 21:00:47 -
2022-08-20 14:04:42
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
