Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間3年前 (2022/11/21 23:21)推噓8(8推 0噓 2→)

留言10則, 8人參與討論串112/719 (看更多)

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