algorithm - 计算二维数组中 block 组的总数？

Question

假设您已给出一个包含值(0 或 1)的二维数组。

计算给定数组中相邻 1 的组总数。

示例1:
1, 0, 0
0, 0, 0
0, 0, 1

答案:2

说明:在上例中，单个 1 的 block 也被视为一组。

---

示例2:
1, 1, 0, 1, 1, 0
0, 1, 0, 0, 0, 1
0, 1, 0, 1, 1, 0
0, 1, 1, 0, 0, 0

答案:1

说明:在上面的例子中，一组1的 block 与至少一个1的 block 相邻。

---

我的解决方案:https://play.golang.org/p/nyw4lm6yrQ1

但是看起来，时间复杂度是O(n^2)

Answer 1

其著名的岛屿数量问题。 您可以通过保留访问过的单元格的 bool 矩阵来执行 dfs 来轻松解决此问题。

class Graph: 

    def __init__(self, row, col, g): 
        self.ROW = row 
        self.COL = col 
        self.graph = g 

# to check validity of cell
    def isSafe(self, i, j, visited): 
        return (i >= 0 and i < self.ROW and 
                j >= 0 and j < self.COL and 
                not visited[i][j] and self.graph[i][j]) 


    def DFS(self, i, j, visited):

        row = [-1, -1, -1,  0, 0,  1, 1, 1]; 
        col = [-1,  0,  1, -1, 1, -1, 0, 1]; 


        visited[i][j] = True

        # check all 8 neighbours and mark them visited
        # as they will be part of group
        for k in range(8): 
            if self.isSafe(i + row[k], j + col[k], visited): 
                self.DFS(i + row[k], j + col[k], visited) 


    def group(self): 

        visited = [[False for j in range(self.COL)]for i in range(self.ROW)] 

        count = 0
        for i in range(self.ROW): 
            for j in range(self.COL): 
                # traverse not visited cell
                if visited[i][j] == False and self.graph[i][j] == 1: 
                    self.DFS(i, j, visited) 
                    count += 1

        return count

`

g = [[1, 1, 0, 0, 0], 
    [0, 1, 0, 0, 1], 
    [1, 0, 0, 1, 1], 
    [0, 0, 0, 0, 0], 
    [1, 0, 1, 0, 1]]
graphe = graph(len(g),len(g[0]),g)
print(graphe.group())