C++实现，使用BFS：
struct POS
{
int x;
int y;
POS(int newx, int newy): x(newx), y(newy) {}
}; class Solution {
public:
void solve(vector<vector<char>> &board) {
if(board.empty() || board[].empty())
return;
int m = board.size();
int n = board[].size();
for(int i = ; i < m; i ++)
{
for(int j = ; j < n; j ++)
{
if(board[i][j] == 'O')
{
if(i == || i == m- || j == || j == n-)
{// remain 'O' on the boundry
bfs(board, i, j, m, n);
}
}
}
}
for(int i = ; i < m; i ++)
{
for(int j = ; j < n; j ++)
{
if(board[i][j] == 'O')
board[i][j] = 'X';
else if(board[i][j] == '*')
board[i][j] = 'O';
}
}
}
void bfs(vector<vector<char>> &board, int i, int j, int m, int n)
{
stack<POS*> stk;
POS* pos = new POS(i, j);
stk.push(pos);
board[i][j] = '*';
while(!stk.empty())
{
POS* top = stk.top();
if(top->x > && board[top->x-][top->y] == 'O')
{
POS* up = new POS(top->x-, top->y);
stk.push(up);
board[up->x][up->y] = '*';
continue;
}
if(top->x < m- && board[top->x+][top->y] == 'O')
{
POS* down = new POS(top->x+, top->y);
stk.push(down);
board[down->x][down->y] = '*';
continue;
}
if(top->y > && board[top->x][top->y-] == 'O')
{
POS* left = new POS(top->x, top->y-);
stk.push(left);
board[left->x][left->y] = '*';
continue;
}
if(top->y < n- && board[top->x][top->y+] == 'O')
{
POS* right = new POS(top->x, top->y+);
stk.push(right);
board[right->x][right->y] = '*';
continue;
}
stk.pop();
}
}
};
补充一个python的实现，使用DFS：
class Solution:
def dfs(self,board,i,j,m,n,visited,direction):
if i < 0 or i >= m or j < 0 or j >= n or visited[i][j] == 1:
return
if board[i][j] == 'O':
board[i][j] = '*'
visited[i][j] = 1 for dirt in direction:
if dirt[0] == 0 and dirt[1] == 0:
continue
x = i + dirt[0]
y = j + dirt[1]
self.dfs(board,x,y,m,n,visited,direction) def solve(self, board: 'List[List[str]]') -> None:
m = len(board)#行
if m == 0:
return
n = len(board[0])#列
if n == 0:
return
visited = [[0 for _ in range(n)]for _ in range(m)]
direction = [[-1,0],[1,0],[0,-1],[0,1]]
for i in range(m):
for j in range(n):
if board[i][j] == 'O' and (i == 0 or i == m-1 or j == 0 or j == n-1):
self.dfs(board,i,j,m,n,visited,direction) for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '*':
board[i][j] = 'O'