# 130. Surrounded Regions
Problem Link (opens new window)
You are given an m x n matrix board consisting of multiple characters 'X' and 'O'. Find all regions surrounded by 'X' and fill these regions with 'X'.
- Input:
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] - Output:
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]] - Explanation: Surrounded regions won't exist on the border, which means that any 'O' on the border will not be filled with 'X'. Any 'O' that is not on the border and not connected to an 'O' on the border will ultimately be filled with 'X'. Any two elements are considered "connected" if they are adjacent horizontally or vertically.
# Plan
This problem is exactly the reverse of Problem 1020. Number of Enclaves (opens new window). Instead of counting the empty spaces in the middle, this problem requires changing 'O's in the middle to 'X'.
Thus, the approach is essentially the same.
Still starting from the border of the map, mark all adjacent 'O's, and then traverse the map again. If an 'O' hasn't been marked, it's in the middle of the map, change it to 'X'.
Some of you might think of defining a separate visited 2D array to mark the 'O's around the border, and when traversing the map, simultaneously check the arrays board and visited to decide whether to change 'O' to 'X'.
This is actually a bit troublesome. You don’t need extra space; you can directly change the value in board to something special to mark the 'O's around the border.
Step 1: Perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to change all 'O's around the border of the map to 'A', as illustrated below:
Step 2: Traverse the map again, change all 'O's to 'X' (the ones in the middle of the map), and change 'A' back to 'O' (retaining the 'O's around the border), as shown below:
The complete C++ code below uses DFS. Both DFS and BFS approaches are feasible.
class Solution {
private:
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // Store four directions
void dfs(vector<vector<char>>& board, int x, int y) {
board[x][y] = 'A';
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (nextx < 0 || nextx >= board.size() || nexty < 0 || nexty >= board[0].size()) continue;
if (board[nextx][nexty] == 'X' || board[nextx][nexty] == 'A') continue;
dfs(board, nextx, nexty);
}
}
public:
void solve(vector<vector<char>>& board) {
int n = board.size(), m = board[0].size();
for (int i = 0; i < n; i++) {
if (board[i][0] == 'O') dfs(board, i, 0);
if (board[i][m - 1] == 'O') dfs(board, i, m - 1);
}
for (int j = 0; j < m; j++) {
if (board[0][j] == 'O') dfs(board, 0, j);
if (board[n - 1][j] == 'O') dfs(board, n - 1, j);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == 'A') board[i][j] = 'O';
}
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Other Language Versions
# Java
// Breadth-First Search
// Using a visited array for marking
class Solution {
private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // Four directions
public void solve(char[][] board) {
int rowSize = board.length, colSize = board[0].length;
boolean[][] visited = new boolean[rowSize][colSize];
Queue<int[]> queue = new ArrayDeque<>();
for (int row = 0; row < rowSize; row++) {
if (board[row][0] == 'O') {
visited[row][0] = true;
queue.add(new int[]{row, 0});
}
if (board[row][colSize - 1] == 'O') {
visited[row][colSize - 1] = true;
queue.add(new int[]{row, colSize - 1});
}
}
for (int col = 1; col < colSize - 1; col++) {
if (board[0][col] == 'O') {
visited[0][col] = true;
queue.add(new int[]{0, col});
}
if (board[rowSize - 1][col] == 'O') {
visited[rowSize - 1][col] = true;
queue.add(new int[]{rowSize - 1, col});
}
}
while (!queue.isEmpty()) {
int[] current = queue.poll();
for (int[] pos : position) {
int row = current[0] + pos[0], col = current[1] + pos[1];
if (row < 0 || row >= rowSize || col < 0 || col >= colSize) continue;
if (visited[row][col] || board[row][col] != 'O') continue;
visited[row][col] = true;
queue.add(new int[]{row, col});
}
}
for (int row = 0; row < rowSize; row++) {
for (int col = 0; col < colSize; col++) {
if (board[row][col] == 'O' && !visited[row][col]) board[row][col] = 'X';
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// Breadth-First Search
// Directly modify the board's value to a special value
class Solution {
private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // Four directions
public void solve(char[][] board) {
int rowSize = board.length, colSize = board[0].length;
Queue<int[]> queue = new ArrayDeque<>();
for (int row = 0; row < rowSize; row++) {
if (board[row][0] == 'O') queue.add(new int[]{row, 0});
if (board[row][colSize - 1] == 'O') queue.add(new int[]{row, colSize - 1});
}
for (int col = 1; col < colSize - 1; col++) {
if (board[0][col] == 'O') queue.add(new int[]{0, col});
if (board[rowSize - 1][col] == 'O') queue.add(new int[]{rowSize - 1, col});
}
while (!queue.isEmpty()) {
int[] current = queue.poll();
board[current[0]][current[1]] = 'A';
for (int[] pos : position) {
int row = current[0] + pos[0], col = current[1] + pos[1];
if (row < 0 || row >= rowSize || col < 0 || col >= colSize) continue;
if (board[row][col] != 'O') continue;
queue.add(new int[]{row, col});
}
}
for (int row = 0; row < rowSize; row++) {
for (int col = 0; col < colSize; col++) {
if (board[row][col] == 'A') board[row][col] = 'O';
else if (board[row][col] == 'O') board[row][col] = 'X';
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// BFS using a helper function
class Solution {
int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public void solve(char[][] board) {
for (int i = 0; i < board.length; i++) {
if (board[i][0] == 'O') bfs(board, i, 0);
if (board[i][board[0].length - 1] == 'O') bfs(board, i, board[0].length - 1);
}
for (int j = 1; j < board[0].length - 1; j++) {
if (board[0][j] == 'O') bfs(board, 0, j);
if (board[board.length - 1][j] == 'O') bfs(board, board.length - 1, j);
}
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] == 'A') board[i][j] = 'O';
}
}
}
private void bfs(char[][] board, int x, int y) {
Queue<Integer> que = new LinkedList<>();
board[x][y] = 'A';
que.offer(x);
que.offer(y);
while (!que.isEmpty()) {
int currX = que.poll();
int currY = que.poll();
for (int i = 0; i < 4; i++) {
int nextX = currX + dir[i][0];
int nextY = currY + dir[i][1];
if (nextX < 0 || nextY < 0 || nextX >= board.length || nextY >= board[0].length)
continue;
if (board[nextX][nextY] == 'X' || board[nextX][nextY] == 'A')
continue;
bfs(board, nextX, nextY);
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Depth-First Search using a visited array for marking
class Solution {
private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // Four directions
public void dfs(char[][] board, int row, int col, boolean[][] visited) {
for (int[] pos : position) {
int nextRow = row + pos[0], nextCol = col + pos[1];
if (nextRow < 0 || nextRow >= board.length || nextCol < 0 || nextCol >= board[0].length)
continue;
if (visited[nextRow][nextCol] || board[nextRow][nextCol] != 'O') continue;
visited[nextRow][nextCol] = true;
dfs(board, nextRow, nextCol, visited);
}
}
public void solve(char[][] board) {
int rowSize = board.length, colSize = board[0].length;
boolean[][] visited = new boolean[rowSize][colSize];
for (int row = 0; row < rowSize; row++) {
if (board[row][0] == 'O' && !visited[row][0]) {
visited[row][0] = true;
dfs(board, row, 0, visited);
}
if (board[row][colSize - 1] == 'O' && !visited[row][colSize - 1]) {
visited[row][colSize - 1] = true;
dfs(board, row, colSize - 1, visited);
}
}
for (int col = 1; col < colSize - 1; col++) {
if (board[0][col] == 'O' && !visited[0][col]) {
visited[0][col] = true;
dfs(board, 0, col, visited);
}
if (board[rowSize - 1][col] == 'O' && !visited[rowSize - 1][col]) {
visited[rowSize - 1][col] = true;
dfs(board, rowSize - 1, col, visited);
}
}
for (int row = 0; row < rowSize; row++) {
for (int col = 0; col < colSize; col++) {
if (board[row][col] == 'O' && !visited[row][col]) board[row][col] = 'X';
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Depth-First Search
// Directly modify the board's value to a special value
class Solution {
private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // Four directions
public void dfs(char[][] board, int row, int col) {
for (int[] pos : position) {
int nextRow = row + pos[0], nextCol = col + pos[1];
if (nextRow < 0 || nextRow >= board.length || nextCol < 0 || nextCol >= board[0].length)
continue;
if (board[nextRow][nextCol] != 'O') continue;
board[nextRow][nextCol] = 'A';
dfs(board, nextRow, nextCol);
}
}
public void solve(char[][] board) {
int rowSize = board.length, colSize = board[0].length;
for (int row = 0; row < rowSize; row++) {
if (board[row][0] == 'O') {
board[row][0] = 'A';
dfs(board, row, 0);
}
if (board[row][colSize - 1] == 'O') {
board[row][colSize - 1] = 'A';
dfs(board, row, colSize - 1);
}
}
for (int col = 1; col < colSize - 1; col++) {
if (board[0][col] == 'O') {
board[0][col] = 'A';
dfs(board, 0, col);
}
if (board[rowSize - 1][col] == 'O') {
board[rowSize - 1][col] = 'A';
dfs(board, rowSize - 1, col);
}
}
for (int row = 0; row < rowSize; row++) {
for (int col = 0; col < colSize; col++) {
if (board[row][col] == 'O') board[row][col] = 'X';
else if (board[row][col] == 'A') board[row][col] = 'O';
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// Depth-First Search (with termination condition)
class Solution {
int[][] dir ={{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public void solve(char[][] board) {
for (int i = 0; i < board.length; i++) {
if (board[i][0] == 'O') dfs(board, i, 0);
if (board[i][board[0].length - 1] == 'O') dfs(board, i, board[0].length - 1);
}
for (int j = 1 ; j < board[0].length - 1; j++) {
if (board[0][j] == 'O') dfs(board, 0, j);
if (board[board.length - 1][j] == 'O') dfs(board, board.length - 1, j);
}
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] == 'A') board[i][j] = 'O';
}
}
}
private void dfs(char[][] board, int x, int y) {
if (board[x][y] == 'X' || board[x][y] == 'A')
return;
board[x][y] = 'A';
for (int i = 0; i < 4; i++) {
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
if (nextX < 0 || nextY < 0 || nextX >= board.length || nextY >= board[0].length)
continue;
dfs(board, nextX, nextY);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Python3
# Depth-First Search
class Solution:
dir_list = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
row_size = len(board)
column_size = len(board[0])
visited = [[False] * column_size for _ in range(row_size)]
for i in range(column_size):
if board[0][i] == "O" and not visited[0][i]:
self.dfs(board, 0, i, visited)
if board[row_size-1][i] == "O" and not visited[row_size-1][i]:
self.dfs(board, row_size-1, i, visited)
for i in range(1, row_size-1):
if board[i][0] == "O" and not visited[i][0]:
self.dfs(board, i, 0, visited)
if board[i][column_size-1] == "O" and not visited[i][column_size-1]:
self.dfs(board, i, column_size-1, visited)
for i in range(row_size):
for j in range(column_size):
if board[i][j] == "A":
board[i][j] = "O"
elif board[i][j] == "O":
board[i][j] = "X"
def dfs(self, board, x, y, visited):
if visited[x][y] or board[x][y] == "X":
return
visited[x][y] = True
board[x][y] = "A"
for i in range(4):
new_x = x + self.dir_list[i][0]
new_y = y + self.dir_list[i][1]
if new_x >= len(board) or new_y >= len(board[0]) or new_x < 0 or new_y < 0:
continue
self.dfs(board, new_x, new_y, visited)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# JavaScript
/**
* @description Depth-First Search
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
function solve(board) {
const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const [rowSize, colSize] = [board.length, board[0].length];
function dfs(board, x, y) {
board[x][y] = 'A';
for (let i = 0; i < 4; i++) {
const nextX = dir[i][0] + x;
const nextY = dir[i][1] + y;
if (nextX < 0 || nextX >= rowSize || nextY < 0 || nextY >= colSize) {
continue;
}
if (board[nextX][nextY] === 'O') {
dfs(board, nextX, nextY);
}
}
}
for (let i = 0; i < rowSize; i++) {
if (board[i][0] === 'O') {
dfs(board, i, 0);
}
if (board[i][colSize - 1] === 'O') {
dfs(board, i, colSize - 1);
}
}
for (let i = 1; i < colSize - 1; i++) {
if (board[0][i] === 'O') {
dfs(board, 0, i);
}
if (board[rowSize - 1][i] === 'O') {
dfs(board, rowSize - 1, i);
}
}
for (let i = 0; i < rowSize; i++) {
for (let k = 0; k < colSize; k++) {
if (board[i][k] === 'A') {
board[i][k] = 'O';
} else if (board[i][k] === 'O') {
board[i][k] = 'X';
}
}
}
}
/**
* @description Breadth-First Search
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
function solve(board) {
const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const [rowSize, colSize] = [board.length, board[0].length];
function bfs(board, x, y) {
board[x][y] = 'A';
const stack = [y, x];
while (stack.length !== 0) {
const top = [stack.pop(), stack.pop()];
for (let i = 0; i < 4; i++) {
const nextX = dir[i][0] + top[0];
const nextY = dir[i][1] + top[1];
if (nextX < 0 || nextX >= rowSize || nextY < 0 || nextY >= colSize) {
continue;
}
if (board[nextX][nextY] === 'O') {
board[nextX][nextY] = 'A';
stack.push(nextY, nextX);
}
}
}
for (let i = 0; i < 4; i++) {
const nextX = dir[i][0] + x;
const nextY = dir[i][1] + y;
if (nextX < 0 || nextX >= rowSize || nextY < 0 || nextY >= colSize) {
continue;
}
if (board[nextX][nextY] === 'O') {
dfs(board, nextX, nextY);
}
}
}
for (let i = 0; i < rowSize; i++) {
if (board[i][0] === 'O') {
bfs(board, i, 0);
}
if (board[i][colSize - 1] === 'O') {
bfs(board, i, colSize - 1);
}
}
for (let i = 1; i < colSize - 1; i++) {
if (board[0][i] === 'O') {
bfs(board, 0, i);
}
if (board[rowSize - 1][i] === 'O') {
bfs(board, rowSize - 1, i);
}
}
for (let i = 0; i < rowSize; i++) {
for (let k = 0; k < colSize; k++) {
if (board[i][k] === 'A') {
board[i][k] = 'O';
} else if (board[i][k] === 'O') {
board[i][k] = 'X';
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
# Go
DFS:
var DIRECTIONS = [4][2]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
func solve(board [][]byte) {
rows, cols := len(board), len(board[0])
for i := 0; i < rows; i++ {
if board[i][0] == 'O' {
dfs(board, i, 0)
}
if board[i][cols-1] == 'O' {
dfs(board, i, cols-1)
}
}
for j := 0; j < cols; j++ {
if board[0][j] == 'O' {
dfs(board, 0, j)
}
if board[rows-1][j] == 'O' {
dfs(board, rows-1, j)
}
}
for _, r := range board {
for j, c := range r {
if c == 'A' {
r[j] = 'O'
continue
}
if c == 'O' {
r[j] = 'X'
}
}
}
}
func dfs(board [][]byte, i, j int) {
board[i][j] = 'A'
for _, d := range DIRECTIONS {
x, y := i+d[0], j+d[1]
if x < 0 || x >= len(board) || y < 0 || y >= len(board[0]) {
continue
}
if board[x][y] == 'O' {
dfs(board, x, y)
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
BFS:
var DIRECTIONS = [4][2]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
func solve(board [][]byte) {
rows, cols := len(board), len(board[0])
for i := 0; i < rows; i++ {
if board[i][0] == 'O' {
bfs(board, i, 0)
}
if board[i][cols-1] == 'O' {
bfs(board, i, cols-1)
}
}
for j := 0; j < cols; j++ {
if board[0][j] == 'O' {
bfs(board, 0, j)
}
if board[rows-1][j] == 'O' {
bfs(board, rows-1, j)
}
}
for _, r := range board {
for j, c := range r {
if c == 'A' {
r[j] = 'O'
continue
}
if c == 'O' {
r[j] = 'X'
}
}
}
}
func bfs(board [][]byte, i, j int) {
queue := [][]int{{i, j}}
board[i][j] = 'A'
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
for _, d := range DIRECTIONS {
x, y := cur[0]+d[0], cur[1]+d[1]
if x < 0 || x >= len(board) || y < 0 || y >= len(board[0]) {
continue
}
if board[x][y] == 'O' {
board[x][y] = 'A'
queue = append(queue, []int{x, y})
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# Rust
DFS:
impl Solution {
const DIRECTIONS: [(isize, isize); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)];
pub fn solve(board: &mut Vec<Vec<char>>) {
let (rows, cols) = (board.len(), board[0].len());
for i in 0..rows {
if board[i][0] == 'O' {
Self::dfs(board, i, 0);
}
if board[i][cols - 1] == 'O' {
Self::dfs(board, i, cols - 1);
}
}
for j in 0..cols {
if board[0][j] == 'O' {
Self::dfs(board, 0, j);
}
if board[rows - 1][j] == 'O' {
Self::dfs(board, rows - 1, j);
}
}
for v in board.iter_mut() {
for c in v.iter_mut() {
if *c == 'A' {
*c = 'O';
continue;
}
if *c == 'O' {
*c = 'X';
}
}
}
}
pub fn dfs(board: &mut [Vec<char>], i: usize, j: usize) {
board[i][j] = 'A';
for (d1, d2) in Self::DIRECTIONS {
let (x, y) = (i as isize + d1, j as isize + d2);
if x < 0 || x >= board.len() as isize || y < 0 || y >= board[0].len() as isize {
continue;
}
let (x, y) = (x as usize, y as usize);
if board[x][y] == 'O' {
Self::dfs(board, x, y);
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
BFS:
use std::collections::VecDeque;
impl Solution {
const DIRECTIONS: [(isize, isize); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)];
pub fn solve(board: &mut Vec<Vec<char>>) {
let (rows, cols) = (board.len(), board[0].len());
for i in 0..rows {
if board[i][0] == 'O' {
Self::bfs(board, i, 0);
}
if board[i][cols - 1] == 'O' {
Self::bfs(board, i, cols - 1);
}
}
for j in 0..cols {
if board[0][j] == 'O' {
Self::bfs(board, 0, j);
}
if board[rows - 1][j] == 'O' {
Self::bfs(board, rows - 1, j);
}
}
for v in board.iter_mut() {
for c in v.iter_mut() {
if *c == 'A' {
*c = 'O';
continue;
}
if *c == 'O' {
*c = 'X';
}
}
}
}
pub fn bfs(board: &mut [Vec<char>], i: usize, j: usize) {
let mut queue = VecDeque::from([(i, j)]);
board[i][j] = 'A';
while let Some((i, j)) = queue.pop_front() {
for (d1, d2) in Self::DIRECTIONS {
let (x, y) = (i as isize + d1, j as isize + d2);
if x < 0 || x >= board.len() as isize || y < 0 || y >= board[0].len() as isize {
continue;
}
let (x, y) = (x as usize, y as usize);
if board[x][y] == 'O' {
board[x][y] = 'A';
queue.push_back((x, y));
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
Copyright © 2025 keetcoder