105.有向圖的完全可達性
題目鏈接:101. 孤島的總面積
文章講解:代碼隨想錄
視頻講解:圖論:島嶼問題再出新花樣 | 深搜優先搜索 | 卡碼網:101.孤島總面積_嗶哩嗶哩_bilibili
思路:?
1.確認遞歸函數,參數
需要傳入地圖,需要知道當前我們拿到的key,以至于去下一個房間。
同時還需要一個數組,用來記錄我們都走過了哪些房間,這樣好知道最后有沒有把所有房間都遍歷的,可以定義一個一維數組。
2.確認終止條件
首先明確,本題中什么叫做處理,visited數組來記錄訪問過的節點,該節點默認數組里元素都是false,把元素標記為true就是處理本節點了。
如果我們是處理當前訪問的節點,當前訪問的節點如果是 true ,說明是訪問過的節點,那就終止本層遞歸,如果不是true,我們就把它賦值為true,因為這是我們處理本層遞歸的節點
3.處理目前搜索節點出發的路徑
本題是需要判斷1節點是否能到所有節點,那么我們就沒有必要回溯去撤銷操作了,只要遍歷過的節點一律都標記上。
(什么時候需要回溯操作,當我們需要搜索一條可行路徑的時候,就需要回溯操作了,因為沒有回溯,就沒法“調頭”。)
106.島嶼的周長
題目鏈接:106. 島嶼的周長
文章講解:代碼隨想錄
思路:?
計算出總的島嶼數量,邊的總的變數為:島嶼數量 * 4,
然后看陸地是否相鄰,有一對相鄰兩個陸地,邊的總數就要減2