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