-
Notifications
You must be signed in to change notification settings - Fork 2
/
0130-surrounded-regions.rs
96 lines (89 loc) · 2.34 KB
/
0130-surrounded-regions.rs
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
struct Solution;
impl Solution {
pub fn solve(board: &mut Vec<Vec<char>>) {
if board.is_empty() {
return;
}
let (rows, cols) = (board.len(), board[0].len());
// Step 1: On all 4 borders of board, change 'O' and all its neighbor
// 'O' elements to a temporary '*'.
for r in 0..rows {
if board[r][0] == 'O' {
Self::dfs(board, r, 0, rows, cols);
}
if board[r][cols - 1] == 'O' {
Self::dfs(board, r, cols - 1, rows, cols);
}
}
for c in 0..cols {
if board[0][c] == 'O' {
Self::dfs(board, 0, c, rows, cols);
}
if board[rows - 1][c] == 'O' {
Self::dfs(board, rows - 1, c, rows, cols);
}
}
for r in 0..rows {
for c in 0..cols {
board[r][c] = match board[r][c] {
// Step 2: change all (remaining) 'O' to 'X'
'O' => 'X',
// Step 3: change all temporary '*' back to 'O'
'*' => 'O',
ch @ _ => ch,
};
}
}
}
fn dfs(board: &mut Vec<Vec<char>>, r: usize, c: usize, rows: usize, cols: usize) {
if board[r][c] != 'O' {
return;
}
board[r][c] = '*';
if r + 1 < rows {
Self::dfs(board, r + 1, c, rows, cols);
}
if c + 1 < cols {
Self::dfs(board, r, c + 1, rows, cols);
}
if r > 0 {
Self::dfs(board, r - 1, c, rows, cols);
}
if c > 0 {
Self::dfs(board, r, c - 1, rows, cols);
}
}
}
fn convert(board: &str) -> Vec<Vec<char>> {
let mut result = Vec::new();
for line in board.trim().split('\n') {
let mut row = Vec::new();
for ch in line.chars() {
if ch.is_ascii_alphabetic() {
row.push(ch);
}
}
result.push(row);
}
result
}
fn main() {
let mut board = convert(
r#"
X X X X
X O O X
X X O X
X O X X
"#,
);
let result = convert(
r#"
X X X X
X X X X
X X X X
X O X X
"#,
);
Solution::solve(&mut board);
assert_eq!(result, board);
}