• Time:O(mn)
• Space:O(1)

## C++

``````class Solution {
public:
void solve(vector<vector<char>>& board) {
if (board.empty())
return;

const int m = board.size();
const int n = board[0].size();
const vector<int> dirs{0, 1, 0, -1, 0};
queue<pair<int, int>> q;

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i * j == 0 || i == m - 1 || j == n - 1)
if (board[i][j] == 'O') {
q.emplace(i, j);
board[i][j] = '*';
}

// mark grids that stretch from four sides with '*'
while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (board[x][y] != 'O')
continue;
q.emplace(x, y);
board[x][y] = '*';
}
}

for (vector<char>& row : board)
for (char& c : row)
if (c == '*')
c = 'O';
else if (c == 'O')
c = 'X';
}
};
``````

## JAVA

``````class Solution {
public void solve(char[][] board) {
if (board.length == 0)
return;

final int m = board.length;
final int n = board[0].length;
final int[] dirs = {0, 1, 0, -1, 0};
Queue<int[]> q = new ArrayDeque<>();

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i * j == 0 || i == m - 1 || j == n - 1)
if (board[i][j] == 'O') {
q.offer(new int[] {i, j});
board[i][j] = '*';
}

// mark grids that stretch from four sides with '*'
while (!q.isEmpty()) {
final int i = q.peek()[0];
final int j = q.poll()[1];
for (int k = 0; k < 4; ++k) {
final int x = i + dirs[k];
final int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (board[x][y] != 'O')
continue;
q.offer(new int[] {x, y});
board[x][y] = '*';
}
}

for (char[] row : board)
for (int i = 0; i < row.length; ++i)
if (row[i] == '*')
row[i] = 'O';
else if (row[i] == 'O')
row[i] = 'X';
}
}
``````

## Python

``````class Solution:
def solve(self, board: List[List[str]]) -> None:
if not board:
return

m = len(board)
n = len(board[0])
dirs = [0, 1, 0, -1, 0]
q = deque()

for i in range(m):
for j in range(n):
if i * j == 0 or i == m - 1 or j == n - 1:
if board[i][j] == 'O':
q.append((i, j))
board[i][j] = '*'

# mark grids that stretch from four sides with '*'
while q:
i, j = q.popleft()
for k in range(4):
x = i + dirs[k]
y = j + dirs[k + 1]
if x < 0 or x == m or y < 0 or y == n:
continue
if board[x][y] != 'O':
continue
q.append((x, y))
board[x][y] = '*'

for row in board:
for i, c in enumerate(row):
row[i] = 'O' if c == '*' else 'X'
``````

• Time:O(mn)
• Space:O(1)

## C++

``````class Solution {
public:
void solve(vector<vector<char>>& board) {
if (board.empty())
return;

const int m = board.size();
const int n = board[0].size();

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i * j == 0 || i == m - 1 || j == n - 1)
dfs(board, i, j);

for (vector<char>& row : board)
for (char& c : row)
if (c == '*')
c = 'O';
else if (c == 'O')
c = 'X';
}

private:
// mark 'O' grids that stretch from four sides with '*'
void dfs(vector<vector<char>>& board, int i, int j) {
if (i < 0 || i == board.size() || j < 0 || j == board[0].size())
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);
}
};
``````

## JAVA

``````class Solution {
public void solve(char[][] board) {
if (board.length == 0)
return;

final int m = board.length;
final int n = board[0].length;

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i * j == 0 || i == m - 1 || j == n - 1)
dfs(board, i, j);

for (char[] row : board)
for (int i = 0; i < row.length; ++i)
if (row[i] == '*')
row[i] = 'O';
else if (row[i] == 'O')
row[i] = 'X';
}

// mark 'O' grids that stretch from four sides with '*'
private void dfs(char[][] board, int i, int j) {
if (i < 0 || i == board.length || j < 0 || 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);
}
}
``````

## Python

``````class Solution:
def solve(self, board: List[List[str]]) -> None:
if not board:
return

m = len(board)
n = len(board[0])

def dfs(i: int, j: int) -> None:
if i < 0 or i == m or j < 0 or j == n:
return
if board[i][j] != 'O':
return

board[i][j] = '*'
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)

for i in range(m):
for j in range(n):
if i * j == 0 or i == m - 1 or j == n - 1:
dfs(i, j)

for row in board:
for i, c in enumerate(row):
row[i] = 'O' if c == '*' else 'X'
``````