1.題目
給你一個大小為 n x n 的二元矩陣 grid ，其中 1 表示陸地，0 表示水域，
島 是由四面相連的 1 形成的一個最大組，即不會與非組內的任何其他 1 相連，grid 中 恰好存在兩座島 ，
你可以將任意數量的 0 變為 1 ，以使兩座島連接起來，變成 一座島 ，
回傳必須翻轉的 0 的最小數目，
示例 1：
輸入：grid = [[0,1],[1,0]]
輸出：1示例 2：
輸入：grid = [[0,1,0],[0,0,0],[0,0,1]]
輸出：2示例 3：
輸入：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]]
輸出：1
提示：
n == grid.length == grid[i].length2 <= n <= 100grid[i][j]為0或1grid中恰有兩個島
2.思路
本題的思路為使用并查集劃分島嶼，及使用廣度搜索找到2個島的路徑，
2.1 并查集的實作
2.1.1 初始化
初始時，每個元素都位于一個單獨的集合，表示為一棵只有根節點的樹，方便起見，我們將根節點的父親設為自己，
public void init(int nums[])
{
int length=nums.length;
for(int i=0;i<length;i++)
nums[i]=i;
}2.1.2 合并
如果兩個元素原先是在兩個不同集合，經過判斷是在同一個集合，則需要將兩個集合進行合并，Notes:合并需要改動他們的根節點的指向即可，否則單純改動葉子結點會成環，
public void union(int nums[],int m,int n)//合并
{
find(n,nums)=find(m,nums);
}2.1.3 查詢
找到集合中的根節點，查詢程序中經過的每個元素都屬于該集合，我們可以將其直接連到根節點以加快后續查詢，
public int find(int n,int nums[])//查詢
{
return n==nums[n] ? n:(nums[n]=find(nums[n],nums));
}2.2 廣度搜索
需要設定每個元素是否有被遍歷，及一個初始值為島1的佇列，從島1出發找到島2的值，找到即停止，回傳路徑最小值，在廣度遍歷的程序中，將遍歷的值加入佇列，并更新到達這個值的距離，
//BFS
int min=0;
while(!List1.isEmpty())
{
int index=List1.poll();
int i=index/len;
int j=index%len;
if((j+1)<len && fw[i][j+1] == false)
{
int a=i*len+j+1;
List1.offer(i*len+j+1);
dis[i][j+1]=dis[i][j]+1;
fw[i][j+1]=true;
if(List2.indexOf(a)!=-1)
{
System.out.println("j+1:"+i+j);
return dis[i][j+1]-1;
}
}
if((i+1)<len && fw[i+1][j] == false)
{
int a=(i+1)*len+j;
List1.offer((i+1)*len+j);
dis[i+1][j]=dis[i][j]+1;
fw[i+1][j]=true;
if(List2.indexOf(a)!=-1)
{
System.out.println("i+1:"+i+j);
return dis[i+1][j]-1;
}
}
if((i-1)>=0 && fw[i-1][j]==false)
{
int a=(i-1)*len+j;
List1.offer(a);
fw[i-1][j]=true;
dis[i-1][j]=dis[i][j]+1;
if(List2.indexOf(a)!=-1)
{
System.out.println("i-1:"+i+j);
return dis[i-1][j]-1;
}
}
if((j-1)>=0 && fw[i][j-1]==false)
{
int a=i*len+j-1;
fw[i][j-1]=true;
List1.offer(i*len+j-1);
dis[i][j-1]=dis[i][j]+1;
if(List2.indexOf(a)!=-1)
{
System.out.println("j-1:"+i+j);
return dis[i][j-1]-1;
}
}
}3.實作代碼
class Solution {
public void init(int nums[])
{
int length=nums.length;
for(int i=0;i<length;i++)
nums[i]=i;
}
public int find(int n,int nums[])//查詢
{
return n==nums[n] ? n:(nums[n]=find(nums[n],nums));
}
public void union(int nums[],int m,int n)//合并
{
//nums[find(n,nums)]=nums[m];
// nums[n]=nums[m];
int length=nums.length;
for(int i=0;i<length;i++)
if(nums[i] ==nums[n])
nums[i]=nums[m];
}
public int shortestBridge(int[][] grid) {
int len=grid.length;
int length=len*len;
int nums[]=new int[length];
init(nums);
int flag=0;
for(int i=0;i<len;i++)
for(int j=0;j<len;j++)
{
int m=i*len+j;
if(grid[i][j] ==1 && flag==0)//島內第一個元素
flag=1;
else if(grid[i][j] ==1 && flag==1)
{
if(i==0 && grid[0][j-1] == 1)
union(nums,j-1,m);
else if(j==0 && grid[i-1][0]==1)
union(nums,(m-len),m);
else if(i>0 && j>0)
{
int x=(i-1)*len+j;
if(grid[i-1][j]==1)
union(nums,x,m);
if(grid[i][j-1]==1)
union(nums,m-1,m);
}
//System.out.println("m:"+m+"nums:"+nums[m]);
}
else if(grid[i][j] == 0)nums[m]=-1;
}
Queue<Integer> List1=new LinkedList<Integer>();
ArrayList<Integer> List2=new ArrayList<Integer>();
flag=-2;
int dis[][]=new int[len][len];
boolean fw[][]=new boolean[len][len];
for(int i=0;i<length;i++)
{
if(nums[i]!=-1 && flag==-2 || nums[i] == flag)
{
List1.offer(i);
flag=nums[i];
int x=i/len;
int y=i%len;
fw[x][y]=true;
}
else if(nums[i]!=-1 && nums[i]!=flag)
{
List2.add(i);
}
}
int List1Lens=List1.size();
//BFS
int min=0;
while(!List1.isEmpty())
{
int index=List1.poll();
int i=index/len;
int j=index%len;
if((j+1)<len && fw[i][j+1] == false)
{
int a=i*len+j+1;
List1.offer(i*len+j+1);
dis[i][j+1]=dis[i][j]+1;
fw[i][j+1]=true;
if(List2.indexOf(a)!=-1)
{
System.out.println("j+1:"+i+j);
return dis[i][j+1]-1;
}
}
if((i+1)<len && fw[i+1][j] == false)
{
int a=(i+1)*len+j;
List1.offer((i+1)*len+j);
dis[i+1][j]=dis[i][j]+1;
fw[i+1][j]=true;
if(List2.indexOf(a)!=-1)
{
System.out.println("i+1:"+i+j);
return dis[i+1][j]-1;
}
}
if((i-1)>=0 && fw[i-1][j]==false)
{
int a=(i-1)*len+j;
List1.offer(a);
fw[i-1][j]=true;
dis[i-1][j]=dis[i][j]+1;
if(List2.indexOf(a)!=-1)
{
System.out.println("i-1:"+i+j);
return dis[i-1][j]-1;
}
}
if((j-1)>=0 && fw[i][j-1]==false)
{
int a=i*len+j-1;
fw[i][j-1]=true;
List1.offer(i*len+j-1);
dis[i][j-1]=dis[i][j]+1;
if(List2.indexOf(a)!=-1)
{
System.out.println("j-1:"+i+j);
return dis[i][j-1]-1;
}
}
}
return 0;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/521828.html
標籤：其他
上一篇：圖的定義和基本術語
下一篇：1028 人口普查