思路:
找到边界的 'O',如果与边界的 'O'是相连的,那么一定是不符合的,对这样的'O'坐标做一个标记,然后对有标记的坐标修改为'O',其他修改为'X'。
代码:
class Solution {
public:
int n,m;
vector<vector<char>> board;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
void solve(vector<vector<char>>& _board) {
board = _board;
n = board.size();
if(!n) return;
m = board[0].size();
for(int i=0;i<n;i++){
if(board[i][0] == 'O') dfs(i,0);
if(board[i][m-1] == 'O') dfs(i,m-1);
}
for(int i = 0;i < m;i++){
if(board[0][i] == 'O') dfs(0,i);
if(board[n-1][i] == 'O') dfs(n-1,i);
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(board[i][j] == '#') board[i][j] = 'O';
else board[i][j] = 'X';
}
}
_board = board;
}
void dfs(int x,int y){
board[x][y] = '#';
for(int i=0;i<4;i++){
int a = x + dx[i];
int b = y + dy[i];
if(a >=0 && a < n && b >= 0 && b < m && board[a][b] == 'O'){
dfs(a,b);
}
}
}
};
评论区