Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-05-21 15:06:03
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:

Links booklink

Contact Us: admin [ a t ] ucptt.com