一個矩陣中只有0和1兩種值,每個位置都可以和自己的上、下、左、右 四個位置相連,如果有一片1連在一起,這個部分叫做一個島,求一個 矩陣中有多少個島?

舉例:

001010

111010

100100

000000

這個矩陣中有三個島

思想對于每一個matrix,從左向右遍歷每一行，整體從上向下遍歷所有的行。如果來到是1的位置，開始一個感染過程，就是從當前位置，把連成一片的1全部變成2。感染過程結束之后，繼續遍歷matrix，直到結束。有多少次感染的過程，就有多少個島

def infect(m,i,j,M,N):if i < 0 or j < 0 or i >= M or j >= N or m[i][j]!=1:return m[i][j] = 2infect(m,i+1,j,M,N)infect(m,i-1,j,M,N)infect(m,i,j+1,M,N)infect(m,i,j-1,M,N)def count(m):if m == None or m[0] == None:return M = len(m)N = len(m[0])res = 0for i in range(M):for j in range(N):if m[i][j] == 1:res +=1infect(m,i,j,M,N)return res

?

如果并行計算，把矩陣拆分開分開計算，之后進行合并，可以加快速度，主要由以下幾步構成

1、并行計算兩部分島的數量以及收集邊界信息

2、利用并查集實現減少島的過程

?

總結

以上是生活随笔為你收集整理的岛问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。