leetcode_rust/
number_of_islands.rs

1#![allow(dead_code)]
2
3// dfs with recursive: time out
4pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
5    use std::iter;
6    let mut visited: Vec<Vec<bool>> = Vec::with_capacity(grid.len());
7    for _ in 0..grid.len() {
8        visited.push(iter::repeat(false).take(grid[0].len()).collect());
9    }
10    let mut count = 0;
11    for i in 0..grid.len() {
12        for j in 0..grid[0].len() {
13            if grid[i][j] == '1' && !visited[i][j] {
14                dfs(&grid, &mut visited, i, j);
15                count += 1;
16            }
17        }
18    }
19
20    count
21}
22
23fn dfs(grid: &Vec<Vec<char>>, mut visited: &mut Vec<Vec<bool>>, i: usize, j: usize) {
24    visited[i][j] = true;
25
26    if i < grid.len() - 1 && !visited[i + 1][j] && grid[i + 1][j] == '1' {
27        dfs(&grid, &mut visited, i + 1, j);
28    }
29    if i > 0 && !visited[i - 1][j] && grid[i - 1][j] == '1' {
30        dfs(&grid, &mut visited, i - 1, j);
31    }
32    if j < grid[0].len() - 1 && !visited[i][j + 1] && grid[i][j + 1] == '1' {
33        dfs(&grid, &mut visited, i, j + 1);
34    }
35    if j > 0 && !visited[i][j - 1] && grid[i][j - 1] == '1' {
36        dfs(&grid, &mut visited, i, j - 1);
37    }
38}
39
40// bfs with loop: time out
41pub fn num_islands2(grid: Vec<Vec<char>>) -> i32 {
42    use std::iter;
43    let mut visited: Vec<Vec<bool>> = Vec::with_capacity(grid.len());
44    for _ in 0..grid.len() {
45        visited.push(iter::repeat(false).take(grid[0].len()).collect());
46    }
47    let mut count = 0;
48    for i in 0..grid.len() {
49        for j in 0..grid[0].len() {
50            if grid[i][j] == '1' && !visited[i][j] {
51                bfs(&grid, &mut visited, i, j);
52                count += 1;
53            }
54        }
55    }
56
57    count
58}
59
60fn bfs(grid: &Vec<Vec<char>>, visited: &mut Vec<Vec<bool>>, i: usize, j: usize) {
61    use std::collections::LinkedList;
62    let mut q = LinkedList::new();
63    q.push_back((i, j));
64    while !q.is_empty() {
65        match q.pop_front() {
66            Some((i, j)) => {
67                visited[i][j] = true;
68                if i + 1 < grid.len() && !visited[i + 1][j] && grid[i + 1][j] == '1' {
69                    q.push_back((i + 1, j));
70                }
71                if i > 0 && !visited[i - 1][j] && grid[i - 1][j] == '1' {
72                    q.push_back((i - 1, j));
73                }
74                if j + 1 < grid[0].len() && !visited[i][j + 1] && grid[i][j + 1] == '1' {
75                    q.push_back((i, j + 1));
76                }
77                if j > 0 && !visited[i][j - 1] && grid[i][j - 1] == '1' {
78                    q.push_back((i, j - 1));
79                }
80            }
81
82            None => unreachable!(),
83        }
84    }
85}
86
87// bfs with loop: reuse the grid
88pub fn num_islands3(mut grid: Vec<Vec<char>>) -> i32 {
89    let mut count = 0;
90    for i in 0..grid.len() {
91        for j in 0..grid[0].len() {
92            if grid[i][j] == '1' {
93                bfs2(&mut grid, i, j);
94                count += 1;
95            }
96        }
97    }
98
99    count
100}
101
102fn bfs2(grid: &mut Vec<Vec<char>>, i: usize, j: usize) {
103    use std::collections::LinkedList;
104    let mut q = LinkedList::new();
105    q.push_back((i, j));
106    while !q.is_empty() {
107        match q.pop_front() {
108            Some((i, j)) => {
109                if i + 1 < grid.len() && grid[i + 1][j] == '1' {
110                    grid[i + 1][j] = '0';
111                    q.push_back((i + 1, j));
112                }
113                if i > 0 && grid[i - 1][j] == '1' {
114                    grid[i - 1][j] = '0';
115                    q.push_back((i - 1, j));
116                }
117                if j + 1 < grid[0].len() && grid[i][j + 1] == '1' {
118                    grid[i][j + 1] = '0';
119                    q.push_back((i, j + 1));
120                }
121                if j > 0 && grid[i][j - 1] == '1' {
122                    grid[i][j - 1] = '0';
123                    q.push_back((i, j - 1));
124                }
125            }
126
127            None => unreachable!(),
128        }
129    }
130}
131
132#[cfg(test)]
133mod tests {
134    use super::*;
135
136    #[test]
137    fn test1() {
138        let grid = vec![
139            vec!['1', '1', '0', '0', '0'],
140            vec!['1', '1', '0', '0', '0'],
141            vec!['0', '0', '1', '0', '0'],
142            vec!['0', '0', '0', '1', '1'],
143        ];
144
145        assert_eq!(num_islands(grid), 3);
146    }
147
148    #[test]
149    fn test2() {
150        let grid = vec![
151            vec!['1', '1', '0', '0', '0'],
152            vec!['1', '1', '0', '0', '0'],
153            vec!['0', '0', '1', '0', '0'],
154            vec!['0', '0', '0', '1', '1'],
155        ];
156
157        assert_eq!(num_islands2(grid), 3);
158    }
159
160    #[test]
161    fn test3() {
162        let grid = vec![
163            vec!['1', '1', '0', '0', '0'],
164            vec!['1', '1', '0', '0', '0'],
165            vec!['0', '0', '1', '0', '0'],
166            vec!['0', '0', '0', '1', '1'],
167        ];
168
169        assert_eq!(num_islands3(grid), 3);
170    }
171}
leetcode_rust/number_of_islands.rs

leetcode_rust/
number_of_islands.rs
