二進制矩陣中的最短路徑【LC1091】
你駕駛出租車行駛在一條有
n個地點的路上。這n個地點從近到遠編號為1到n，你想要從1開到n，通過接乘客訂單盈利。你只能沿著編號遞增的方向前進，不能改變方向。乘客信息用一個下標從 0 開始的二維數(shù)組
rides表示，其中rides[i] = [starti, endi, tipi]表示第i位乘客需要從地點starti前往endi，愿意支付tipi元的小費。每一位 你選擇接單的乘客
i，你可以 盈利endi - starti + tipi元。你同時 最多 只能接一個訂單。給你
n和rides，請你返回在最優(yōu)接單方案下，你能盈利 最多 多少元。**注意：**你可以在一個地點放下一位乘客，并在同一個地點接上另一位乘客。
-
思路
常規(guī)BFS，使用隊列進行BFS，搜索時記錄搜索的輪數(shù)。搜索到一個可以訪問的節(jié)點時，將其入隊。如果搜索到終點時，直接返回當前輪數(shù)；如果隊列為空仍為訪問到終點，那么返回-1；文章來源：http://www.zghlxwxcb.cn/news/detail-479448.html
- 訪問過一個節(jié)點后，為了避免重復訪問直接將給節(jié)點設置為-1
-
實現(xiàn)文章來源地址http://www.zghlxwxcb.cn/news/detail-479448.html
class Solution { public int shortestPathBinaryMatrix(int[][] grid) { // BFS int[][] dirs = {{0, 1}, {1, 0}, {1, 1}, {0, -1}, {-1, 0}, {-1, -1}, {1, -1}, {-1, 1}};// 8個方向？ Deque<int[]> queue = new LinkedList<>(); int n = grid.length; int count = 0; if (grid[0][0] == 0){ queue.add(new int[]{0, 0}); } while(!queue.isEmpty()){ int size = queue.size(); count++; for (int i = 0; i < size; i++){ int[] p = queue.poll(); int x = p[0], y = p[1]; if (x == n - 1 && y == n - 1) return count; for (int[] dir : dirs){ int x1 = x + dir[0], y1 = y + dir[1]; if (x1 >= 0 && y1 >= 0 && x1 <n && y1 < n && grid[x1][y1] != 1){ queue.add(new int[]{x1, y1}); grid[x1][y1] = 1; } } } } return -1; } }- 復雜度
- 時間復雜度： O ( n 2 ) \mathcal{O}(n^2) O(n2)
- 空間復雜度： O ( n 2 ) \mathcal{O}(n^2) O(n2)
- 復雜度
到了這里，關于【每日一題Day218】LC1091 二進制矩陣中的最短路徑 | BFS的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
