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

问题描述

我正在尝试计算2D二进制矩阵中的孤岛(一组相连的1组成一个孤岛)的数量.

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

示例:

[
[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个岛，分别是:

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)

要计算2D矩阵中的孤岛数量，我假设矩阵为图，然后使用DFS类型的算法对孤岛进行计数.

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.

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

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)

我传入参数的矩阵输出错误.我得到7，但是有5个群集.

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.

推荐答案

除了第21行之外，您的算法几乎是正确的:

Your algorithm is almost correct except for the line 21:

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

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

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)

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