Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/06/03 02:06)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串334/719 (看更多)

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ 1091. Shortest Path in Binary Matrix 給你一個矩陣，判斷從0,0開始走，只走格子是0的格子，走到矩陣的最右下角，最少需要走幾步（可以上下左右+斜走），走不到右下角則返回-1。 Example 1: https://assets.leetcode.com/uploads/2021/02/18/example1_1.png

Input: grid = [[0,1],[1,0]] Output: 2 Example 2: https://assets.leetcode.com/uploads/2021/02/18/example2_1.png

Input: grid = [[0,0,0],[1,1,0],[1,1,0]] Output: 4 思路： 1.找最短路徑基本上就是BFS，這題是一個八個方向的BFS，如果有一個點走到最右下他就是最短路徑。 2.可以先在前面把Corner Case處理掉，起點是1不可能走到，起點是0且只有一格一開始就在終點，這些都直接返回。 3.BFS的時候要標記已經處理完的點避免往回走，這邊我是懶得在定義一個visited陣列所以直接走過的標-1。 Java Code： --------------------------------------------------- class Solution { public int shortestPathBinaryMatrix(int[][] grid) { int m = grid.length; int n = grid[0].length; int res = 1; if (grid[0][0] == 1 || grid[m-1][n-1] == 1) { return -1; } if (m == 1 && n == 1) { return res; } Queue<int[]> queue = new LinkedList<>(); grid[0][0] = -1; queue.add(new int[]{0, 0}); int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int[] e = queue.poll(); for (int dir[] : dirs) { int y = e[0] + dir[0]; int x = e[1] + dir[1]; if (y < 0 || x < 0 || y >= m || x >= n || grid[y][x] != 0) { continue; } if (y == m - 1 && x == n - 1) { return res + 1; } queue.add(new int[]{y, x}); grid[y][x] = -1; } } res++; } return -1; } } --------------------------------------------------- 這題是兩天前的題目晚安== -- https://i.imgur.com/CBMFmWk.jpg