在二维二进制矩阵中找到岛屿的数量 [英] In 2D binary matrix find the number of islands

问题描述

我正在尝试计算二维二进制矩阵中的岛数(一组连接的 1 形成一个岛).

示例:

<预><代码>[[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]]

在上面的矩阵中有5个岛，它们是:

第一:(0,0), (0,1), (1,1), (2,0)第二:(1,4)、(2,3)、(2,4)第三:(4,0)第四:(4,2)第五:(4,4)

为了计算二维矩阵中岛屿的数量，我假设矩阵是一个图，然后我使用 DFS 类型的算法来计算岛屿.

我正在跟踪 DFS(一个递归函数)调用的数量，因为图中会有很多组件.

以下是我为此目的编写的代码:

# 计算岛上的 1def count_houses(mat,visited,i,j):# 基本情况如果我＜0 或 i >= len(mat) 或 j <0 或 j >= len(mat[0]) 或访问 [i][j] 为真或 mat[i][j] == 0:返回 0# 标记在 i, j 处访问过访问过[i][j] = 真# cnt 被初始化为 1 因为找到 1cnt = 1# 现在朝所有可能的方向前进(即形成 8 个分支)# 从 i,j 的左上角开始向下到右下角# i,j 的角对于 xrange(i-1, i+2, 1) 中的 r:对于 xrange(j-1, j+2, 1) 中的 c:# 打印 'r:', r# 打印 'c:', c# 不要叫 i, j如果 r != i 和 c != j:cnt += count_houses(mat,visited, r, c)返回 cntdef island_count(mat):房屋 = 列表()集群 = 0行 = len(mat)col = len(mat[0])# 初始化访问矩阵访问 = [[False for i in xrange(col)] for j in xrange(row)]# 遍历矩阵，搜索 1，然后在找到 1 时执行 dfs对于 xrange(row) 中的 i:对于 xrange(col) 中的 j:# 查看在 i, j 处的值是否在 mat 中为 1，在 i, j 处是否为 False in# 访问过如果 mat[i][j] == 1 并且visited[i][j] 为False:集群 += 1h = count_houses(mat,visited, i, j)房子.append(h)打印簇:"，簇还房如果 __name__ == '__main__':垫子 = [[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]]房屋 = island_count(垫子)印刷厂# 打印 '最大房屋数:', max(houses)

我在参数中传递的矩阵输出错误.我得到 7 但有 5 个簇.

我尝试调试代码以查找任何逻辑错误.但我找不到问题出在哪里.

解决方案

你的算法几乎是正确的，除了第 21 行:

如果 r != i 和 c != j:cnt += count_houses(mat,visited, r, c)

相反，您希望使用 or 继续计数，前提是至少有一个坐标与您的中心不同.

如果 r != i 或 c != j:cnt += count_houses(mat,visited, r, c)

另一种更直观的写法如下

if (r, c) != (i, j):cnt += count_houses(mat,visited, r, c)

I am trying to count the number of islands (a group of connected 1s forms an island) in a 2D binary matrix.

Example:

[
[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]
]

In the above matrix there are 5 islands, which are:

First: (0,0), (0,1), (1,1), (2,0)
Second: (1,4), (2,3), (2,4)
Third: (4,0)
Fourth: (4,2)
Fifth: (4,4)

To count the number of island in the 2D matrix, I am assuming the matrix as a Graph and then I am using DFS kind of algorithm to count the islands.

I am keeping track for the number of DFS (a recursive function) calls, because that many components would be there in the Graph.

Below is the code I wrote for this purpose:

# count the 1's in the island
def count_houses(mat, visited, i, j):
    # base case
    if i < 0 or i >= len(mat) or j < 0 or j >= len(mat[0]) or
            visited[i][j] is True or mat[i][j] == 0:
        return 0
    # marking visited at i, j
    visited[i][j] = True
    # cnt is initialized to 1 coz 1 is found
    cnt = 1
    # now go in all possible directions (i.e. form 8 branches)
    # starting from the left upper corner of i,j and going down to right bottom
    # corner of i,j
    for r in xrange(i-1, i+2, 1):
        for c in xrange(j-1, j+2, 1):
            # print 'r:', r
            # print 'c:', c
            # don't call for i, j
            if r != i and c != j:
                cnt += count_houses(mat, visited, r, c)
    return cnt


def island_count(mat):
    houses = list()
    clusters = 0
    row = len(mat)
    col = len(mat[0])
    # initialize the visited matrix
    visited = [[False for i in xrange(col)] for j in xrange(row)]
    # run over matrix, search for 1 and then do dfs when found 1
    for i in xrange(row):
        for j in xrange(col):
            # see if value at i, j is 1 in mat and val at i, j is False in
            # visited
            if mat[i][j] == 1 and visited[i][j] is False:
                clusters += 1
                h = count_houses(mat, visited, i, j)
                houses.append(h)
    print 'clusters:', clusters
    return houses


if __name__ == '__main__':
    mat = [
        [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]
    ]
    houses = island_count(mat)
    print houses
    # print 'maximum houses:', max(houses)

I get a wrong output for the matrix I have passed in argument. I get 7 but there are 5 clusters.

I tried debugging the code for any logical errors. But I couldn't find out where is the problem.

解决方案

Your algorithm is almost correct except for the line 21:

if r != i and c != j:
    cnt += count_houses(mat, visited, r, c)

Instead you want to use or as you want to continue counting provided at least one of the coordinate is not the same as your center.

if r != i or c != j:
    cnt += count_houses(mat, visited, r, c)

An alternate and more intuitive way to write this would be the following

if (r, c) != (i, j):
    cnt += count_houses(mat, visited, r, c)

这篇关于在二维二进制矩阵中找到岛屿的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！