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

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

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

https://leetcode.com/problems/shortest-bridge/description/ 934. Shortest Bridge 給你一二維陣列表示的矩陣，0表示海，1表示陸地，相連的陸地是一個島嶼，這個矩陣恰好存在兩個島嶼，如果想要在兩個島建立一個橋使其兩島嶼相連，最少需要多少長度? Example 1: Input: grid = [[0,1],[1,0]] Output: 1 Example 2: Input: grid = [[0,1,0],[0,0,0],[0,0,1]] Output: 2 Example 3: Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]] Output: 1 思路： 1.在矩陣中找最短路徑第一個要想到BFS。 2.先找到隨便一個島嶼的任意一點，再對該點做一次BFS或DFS把所有相鄰的點蒐集起來，走過的點都標記為-1表示已處理。 3.把先前蒐集的點放進Queue做BFS，對沒被處理過點BFS，一樣標記已經走過的點，直到遇到沒走過的島嶼時，返回當前的距離就是最短橋樑長度。 Java Code： ----------------------------------------------------------- class Solution { public int shortestBridge(int[][] grid) { int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int m = grid.length; int n = grid[0].length; List<int[]> list = new ArrayList<>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { grid[i][j] = -1; list.add(new int[]{i, j}); break; } } if (list.size() > 0) { break; } } int index = 0; while (index < list.size()) { int[] points = list.get(index); for (int[] d : dir) { int y = points[0] + d[0]; int x = points[1] + d[1]; if (y >= m || y < 0 || x >= n || x < 0 || grid[y][x] != 1) continue; grid[y][x] = -1; list.add(new int[]{y, x}); } index++; } Queue<int[]> queue = new LinkedList<>(list); int res = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int[] points = queue.poll(); for (int[] d : dir) { int y = points[0] + d[0]; int x = points[1] + d[1]; if (y >= m || y < 0 || x >= n || x < 0 || grid[y][x] == -1) continue; if (grid[y][x] == 1) { return res; } queue.add(new int[]{y, x}); grid[y][x] = -1; } } res++; } return -1; } } ----------------------------------------------------------- -- https://i.imgur.com/PIoxddO.jpg