Re: [閒聊] 每日LeetCode

1926. Nearest Exit from Entrance in Maze 龍大被困在邊板了，總是忍不住偷看邊板，龍大想要從邊板逃出去他必須要走過一個迷宮 而且走太慢會被邊板仔抓回來，所以龍大要走最短的路線逃走，求出龍大逃出邊板這個 迷宮最短需要走幾步（逃不出去就返回-1）。 +:牆壁不能走 .:道路 Example： https://assets.leetcode.com/uploads/2021/06/04/nearest1-grid.jpg Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] Output: 1 Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3]. Initially, you are at the entrance cell [1,2]. - You can reach [1,0] by moving 2 steps left. - You can reach [0,2] by moving 1 step up. It is impossible to reach [2,3] from the entrance. Thus, the nearest exit is [0,2], which is 1 step away. 思路： 1.一開始用DFS找出口吃了TLE，因為這題是要求最短路徑所以用BFS效率比較好，不用 算出所有的路線（BFS只要找到任意一個出口，該出口必定是最短出口） 2.一開始先把入口設定成牆壁（不能從迷宮入口回走，龍大會回到邊板） 3.然後從起點的上下左右出發用queue來跑BFS，紀錄移動後的座標{X, Y, 距離} 如果遇到邊界表示碰到一個出口，如果這個出口不是起點就返回我們已經走的距離。 4.放入Queue的條件是下個點的位置不是牆壁，我們要把每個走過的地方都標記成牆壁 避免回頭走。 JavaCode： --------------------------------------- class Solution { public int nearestExit(char[][] maze, int[] entrance) { int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; int m = maze.length; int n = maze[0].length; int ey = entrance[0]; int ex = entrance[1]; maze[ey][ex] = '+'; Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[] {ey, ex, 0}); while (!queue.isEmpty()) { int[] curr = queue.poll(); for (int[] direction : directions) { int py = curr[0] + direction[0]; int px = curr[1] + direction[1]; if (px < 0 || py < 0 || px >= n || py >= m) { if (curr[0] == ey && curr[1] == ex) continue; return curr[2]; } if (maze[py][px] == '.') { queue.offer(new int[]{py, px, curr[2] + 1}); maze[py][px] = '+'; } } } return -1; } } --------------------------------------- https://i.imgur.com/acHi4CL.png -- https://i.imgur.com/uiFto42.jpg --
※ 批踢踢實業坊(ptt.cc), 來自: 49.159.111.108 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1669044104.A.ECE.html

推 EMANON231: 靠北 11/21 23:23

推 v03516020: @d******* 11/21 23:25

推 sustainer123: 大師 11/21 23:25

→ SecondRun: BFS 11/21 23:27