資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：從給定矩陣中查詢不同島嶼形狀的數量
假設我們有一個二維二進位制矩陣，我們需要找到給定矩陣中不同島嶼的數量。這裡1代表陸地，0代表水，因此島嶼是一組相鄰的1，其周邊被水包圍。如果兩個島嶼的形狀不同，則它們是唯一的。
因此，如果輸入如下所示：
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
則輸出將為4（不同島嶼以不同的顏色顯示）。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式dfs()。這將接收i, j, k, l
mat[i, j] := 0
將(i − k, j − l)對插入到shape的末尾
如果 i + 1 < mat的行數 且 mat[i + 1, j] 為1，則
dfs(i + 1, j, k, l)
如果 j + 1 < mat的列數 且 mat[i, j + 1] 為1，則
dfs(i, j + 1, k, l)
如果 i − 1 >= 0 且 mat[i − 1, j] 為1，則
dfs(i − 1, j, k, l)
如果 j − 1 >= 0 且 mat[i, j − 1] 為1，則
dfs(i, j − 1, k, l)
在主方法中執行以下操作：
cnt := 0
shapes := 一個新的集合
對於 i 的範圍從 0 到 mat 的行數，執行
對於 j 的範圍從 0 到 mat 的列數，執行
如果 mat[i, j] 為 1，則
shape := 一個新的列表
dfs(i, j, i, j)
如果 shape 不在 shapes 中，則
cnt := cnt + 1
將 shape 插入到 shapes 中
返回 cnt
讓我們看下面的實現來更好地理解：
示例
class Solution: def solve(self, mat): def dfs(i, j, k, l): mat[i][j] = 0 shape.append((i − k, j − l)) if i + 1 < len(mat) and mat[i + 1][j]: dfs(i + 1, j, k, l) if j + 1 < len(mat[0]) and mat[i][j + 1]: dfs(i, j + 1, k, l) if i − 1 >= 0 and mat[i − 1][j]: dfs(i − 1, j, k, l) if j − 1 >= 0 and mat[i][j − 1]: dfs(i, j − 1, k, l) cnt = 0 shapes = set() for i in range(len(mat)): for j in range(len(mat[0])): if mat[i][j]: shape = [] dfs(i, j, i, j) shape = tuple(shape) if shape not in shapes: cnt += 1 shapes.add(shape) return cnt ob = Solution() matrix = [ [1, 0, 0, 0, 0], [1, 0, 1, 0, 1], [0, 1, 1, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1] ] print(ob.solve(matrix))
輸入
[ [1, 0, 0, 0, 0], [1, 0, 1, 0, 1], [0, 1, 1, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1] ]
輸出
4
更新於：2020-12-26
242 次瀏覽
廣告