static const int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
static void dfs(char **board, int r, int c, int rows, int cols) {
if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != 'O')
return;
board[r][c] = '.';
for (int d = 0; d < 4; d++)
dfs(board, r + dirs[d][0], c + dirs[d][1], rows, cols);
}
void solve(char **board, int boardSize, int *boardColSize) {
int rows = boardSize, cols = boardColSize[0];
// 1. mark border-connected 'O's as safe
for (int i = 0; i < rows; i++) {
dfs(board, i, 0, rows, cols);
dfs(board, i, cols - 1, rows, cols);
}
for (int j = 0; j < cols; j++) {
dfs(board, 0, j, rows, cols);
dfs(board, rows - 1, j, rows, cols);
}
// 2. capture leftover 'O's, restore safe ones
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';
}
}
#include <vector>
using namespace std;
class Solution {
public:
void solve(vector<vector<char>> &board) {
rows = board.size();
cols = board[0].size();
// 1. mark border-connected 'O's as safe
for (int i = 0; i < rows; i++) {
dfs(board, i, 0);
dfs(board, i, cols - 1);
}
for (int j = 0; j < cols; j++) {
dfs(board, 0, j);
dfs(board, rows - 1, j);
}
// 2. capture leftover 'O's, restore safe ones
for (auto &row : board)
for (char &cell : row) {
if (cell == 'O')
cell = 'X';
else if (cell == '.')
cell = 'O';
}
}
private:
int rows, cols;
static constexpr int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
void dfs(vector<vector<char>> &board, int r, int c) {
if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != 'O')
return;
board[r][c] = '.';
for (auto [dr, dc] : dirs)
dfs(board, r + dr, c + dc);
}
};
package graphs
var dirs = [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
func solve(board [][]byte) {
rows, cols := len(board), len(board[0])
var dfs func(r, c int)
dfs = func(r, c int) {
if r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != 'O' {
return
}
board[r][c] = '.'
for _, d := range dirs {
dfs(r+d[0], c+d[1])
}
}
// 1. mark border-connected 'O's as safe
for i := 0; i < rows; i++ {
dfs(i, 0)
dfs(i, cols-1)
}
for j := 0; j < cols; j++ {
dfs(0, j)
dfs(rows-1, j)
}
// 2. capture leftover 'O's, restore safe ones
for _, row := range board {
for j, cell := range row {
if cell == 'O' {
row[j] = 'X'
} else if cell == '.' {
row[j] = 'O'
}
}
}
}
class Solution {
private static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
private int rows, cols;
public void solve(char[][] board) {
rows = board.length;
cols = board[0].length;
// 1. mark border-connected 'O's as safe
for (int i = 0; i < rows; i++) {
dfs(board, i, 0);
dfs(board, i, cols - 1);
}
for (int j = 0; j < cols; j++) {
dfs(board, 0, j);
dfs(board, rows - 1, j);
}
// 2. capture leftover 'O's, restore safe ones
for (char[] row : board)
for (int j = 0; j < cols; j++) {
if (row[j] == 'O')
row[j] = 'X';
else if (row[j] == '.')
row[j] = 'O';
}
}
private void dfs(char[][] board, int r, int c) {
if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != 'O')
return;
board[r][c] = '.';
for (int[] d : DIRS)
dfs(board, r + d[0], c + d[1]);
}
}
const DIRS = [
[1, 0],
[0, 1],
[-1, 0],
[0, -1],
];
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function (board) {
const rows = board.length,
cols = board[0].length;
const dfs = (r, c) => {
if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== "O") return;
board[r][c] = ".";
for (const [dr, dc] of DIRS) dfs(r + dr, c + dc);
};
// 1. mark border-connected 'O's as safe
for (let i = 0; i < rows; i++) {
dfs(i, 0);
dfs(i, cols - 1);
}
for (let j = 0; j < cols; j++) {
dfs(0, j);
dfs(rows - 1, j);
}
// 2. capture leftover 'O's, restore safe ones
for (const row of board)
for (let j = 0; j < cols; j++) {
if (row[j] === "O") row[j] = "X";
else if (row[j] === ".") row[j] = "O";
}
};
from typing import List
DIRS = ((1, 0), (0, 1), (-1, 0), (0, -1))
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
rows, cols = len(board), len(board[0])
def dfs(r: int, c: int) -> None:
if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != "O":
return
board[r][c] = "."
for dr, dc in DIRS:
dfs(r + dr, c + dc)
# 1. mark border-connected 'O's as safe
for i in range(rows):
dfs(i, 0)
dfs(i, cols - 1)
for j in range(cols):
dfs(0, j)
dfs(rows - 1, j)
# 2. capture leftover 'O's, restore safe ones
for row in board:
for j, cell in enumerate(row):
if cell == "O":
row[j] = "X"
elif cell == ".":
row[j] = "O"
const DIRS: [(isize, isize); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];
impl Solution {
pub fn solve(board: &mut Vec<Vec<char>>) {
let (rows, cols) = (board.len(), board[0].len());
// 1. mark border-connected 'O's as safe
for i in 0..rows {
Self::dfs(board, i, 0, rows, cols);
Self::dfs(board, i, cols - 1, rows, cols);
}
for j in 0..cols {
Self::dfs(board, 0, j, rows, cols);
Self::dfs(board, rows - 1, j, rows, cols);
}
// 2. capture leftover 'O's, restore safe ones
for cell in board.iter_mut().flatten() {
if *cell == 'O' {
*cell = 'X';
} else if *cell == '.' {
*cell = 'O';
}
}
}
fn dfs(board: &mut Vec<Vec<char>>, r: usize, c: usize, rows: usize, cols: usize) {
if board[r][c] != 'O' {
return;
}
board[r][c] = '.';
for (dr, dc) in DIRS {
// wrapping_add_signed turns -1 at 0 into usize::MAX, caught by the bounds check
let (nr, nc) = (r.wrapping_add_signed(dr), c.wrapping_add_signed(dc));
if nr < rows && nc < cols {
Self::dfs(board, nr, nc, rows, cols);
}
}
}
}