[閒聊] 每日leetcode 75 - Day27

[yam276 (史萊哲林的優等生)]

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
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1752749914.A.E12.html