1926. Nearest Exit from Entrance in Maze
题目：
劳赎走迷宫
走到 m × n 不是墙壁的边缘就通过
找最短路径
思路：
这题有点复杂 所以我还是看了详解
总之这题目有点像是树的 BFS
就是你要从起点开始延伸
你建立一组每次会走的路
let dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)];
以及标记是否走过这条路
然后每次把 queue 延伸
每一轮的新 queue 都是上一轮的下一步
这样会逐渐从入口往外得知可能路径
当遇到第一个碰到出口的时候就会回传 steps
主要难点是同时结合多种判断
有拜访过的点跟墙壁
Code:
use std::collections::VecDeque;
impl Solution {
pub fn nearest_exit(maze: Vec<Vec<char>>, entrance: Vec<i32>) -> i32 {
let m = maze.len();
let n = maze[0].len();
let mut visited = vec![vec![false; n]; m];
let mut queue = VecDeque::new();
let entrance_row = entrance[0] as usize;
let entrance_column = entrance[1] as usize;
queue.push_back((entrance_row, entrance_column, 0));
visited[entrance_row][entrance_column] = true;
while let Some((row, col, steps)) = queue.pop_front() {
if (row == 0 || col == 0 || row == m - 1 || col == n - 1)
&& (row != entrance_row || col != entrance_column)
{
return steps;
}
let dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)];
for (dr, dc) in &dirs {
let new_row = row as i32 + dr;
let new_column = col as i32 + dc;
if new_row < 0 || new_row >= m as i32 ||
new_column < 0 || new_column >= n as i32 {
continue;
}
let new_row = new_row as usize;
let new_column = new_column as usize;
if maze[new_row][new_column] == '+' ||
visited[new_row][new_column] {
continue;
}
queue.push_back((new_row, new_column, steps + 1));
visited[new_row][new_column] = true;
}
}
-1
}
}