aboutsummaryrefslogtreecommitdiff
path: root/other/nearest_exit_maze.rs
diff options
context:
space:
mode:
Diffstat (limited to 'other/nearest_exit_maze.rs')
-rw-r--r--other/nearest_exit_maze.rs37
1 files changed, 37 insertions, 0 deletions
diff --git a/other/nearest_exit_maze.rs b/other/nearest_exit_maze.rs
new file mode 100644
index 0000000..3f314f2
--- /dev/null
+++ b/other/nearest_exit_maze.rs
@@ -0,0 +1,37 @@
+use std::collections::VecDeque;
+use std::collections::HashSet;
+struct Solution;
+
+impl Solution {
+ pub fn nearest_exit(maze: Vec<Vec<char>>, entrance: Vec<i32>) -> i32 {
+ let (mut dq, mut visited) = (VecDeque::new(), HashSet::new());
+ dq.push_back((entrance[0] as usize, entrance[1] as usize, 0));
+ while !dq.is_empty() {
+ while let Some((i, j, c)) = dq.pop_front() {
+ if !visited.insert((i, j)) {
+ continue;
+ }
+ if i == 0 || i == maze.len() - 1 || j == 0 || j == maze[0].len() - 1 {
+ if i != entrance[0] as usize || j != entrance[1] as usize {
+ return c;
+ }
+ }
+ if maze[i][j] == '.' {
+ if i > 0 && maze[i - 1][j] == '.' {
+ dq.push_back((i - 1, j, c + 1));
+ }
+ if i < maze.len() - 1 && maze[i + 1][j] == '.' {
+ dq.push_back((i + 1, j, c + 1));
+ }
+ if j > 0 && maze[i][j - 1] == '.' {
+ dq.push_back((i, j - 1, c + 1));
+ }
+ if j < maze[0].len() - 1 && maze[i][j + 1] == '.' {
+ dq.push_back((i, j + 1, c + 1));
+ }
+ }
+ }
+ }
+ -1
+ }
+}