題目描述
給你一個大小為 n x n 二進制矩陣 grid ，最多 只能將一格 0 變成 1 ，
回傳執行此操作后，grid 中最大的島嶼面積是多少？
島嶼 由一組上、下、左、右四個方向相連的 1 形成，
示例1：
輸入: grid = [[1, 0], [0, 1]]
輸出: 3
解釋: 將一格0變成1，最終連通兩個小島得到面積為 3 的島嶼，
示例2：
輸入: grid = [[1, 1], [1, 0]]
輸出: 4
解釋: 將一格0變成1，島嶼的面積擴大為 4，
示例3：
輸入: grid = [[1, 1], [1, 1]]
輸出: 4
解釋: 沒有0可以讓我們變成1，面積依然為 4，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/making-a-large-island
解答詳情
這是一道DFS+二維+著色的題目，難度為hard，近日在LeetCode上刷DFS相關題的時候遇到的，覺得挺不錯的一題，說一下個人的思路和見解：
如果使用暴力法：對每個海域即二維陣列為0的位置進行dfs算出島嶼最大值，還需要對其置1后恢復，比較麻煩且容易出錯，并且時間復雜度上在LeetCode上是肯定超時的，
其實對于DFS的題來說，一般使用DFS+回溯就能夠解決了，但這畢竟是hard題，對此本人使用著色的方法，即定義一個int型別全域變數；先對二維陣列進行一次DFS，將不同島嶼進行著色區分并計算出填海前（將某個0變成1）的面積；定義一個全域變數Map用于存盤每個島嶼的對應面積，即顏色為key，對應面積為value；對其進行第一次DFS后，所有島嶼完成了著色并計算出填海前的面積，此時再去尋找具有相鄰島嶼的海域進行填海（將某個0變成1），從而得出最大島嶼面積，
class Solution {
//全域Map，key著色，val島嶼面積
private Map<Integer,Integer> islandAreaMap = new HashMap<>();
//全域int，每個島嶼的用color值劃分
private int color = -1;
public int largestIsland(int[][] grid) {
int res = 0;
int m = grid.length;
//先對二維資料進行一次dfs，得出每個島嶼的面積
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < m ; j++){
if(grid[i][j]==1){
color --;//用于區分不同島嶼
int area = dfs(grid,i,j);//通過dfs計算島嶼面積
islandAreaMap.put(color,area);
res = Math.max(res,area);
}
}
}
//尋找相鄰島嶼，填海，找最大值
for(int i = 0 ; i < m ; i++){
for(int j = 0 ; j < m ; j++){
//使用Set標記相鄰島嶼面積
Set<Integer> islandAreaSet = new HashSet<>();
//判斷填海位置是否具有相鄰島嶼，島嶼已被著色
if(grid[i][j]==0){
if(i > 0 && grid[i-1][j]<0){
islandAreaSet.add(grid[i-1][j]);// 將島嶼顏色作為val
}
if(i < m-1 && grid[i+1][j]<0){
islandAreaSet.add(grid[i+1][j]);
}
if(j > 0 && grid[i][j-1]<0){
islandAreaSet.add(grid[i][j-1]);
}
if(j < m-1 && grid[i][j+1]<0){
islandAreaSet.add(grid[i][j+1]);
}
}
//計算填海后島嶼面積
int area = 1;
for(Integer islandColor : islandAreaSet){
area += islandAreaMap.getOrDefault(islandColor,0);
}
res = Math.max(res,area);
}
}
return res;
}
private int dfs(int[][] grid,int i,int j){
int m = grid.length;
//例外退出
if(i < 0 || j < 0 || i >= m || j >= m || grid[i][j] < 1){
return 0;
}
//對同一島嶼進行著色
if(grid[i][j]==1){
grid[i][j] = color;
}
//計算島嶼面積，對垂直/水平分別進行DFS
return 1+dfs(grid,i-1,j)+dfs(grid,i+1,j)+dfs(grid,i,j-1)+dfs(grid,i,j+1);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/297472.html
標籤：其他