查找二维数组子空间的面积？

Question

我正在尝试创建一个函数，给定一个由 0 或 1 组成的二维数组和一组坐标，returns 所选区域的面积与给定坐标的值相同。

例如给定数组：

[[0, 1, 0, 0, 0],
 [0, 1, 0, 0, 0],
 [0, 1, 0, 0, 0],
 [0, 1, 0, 0, 0],
 [0, 1, 0, 0, 0]]

和坐标[0,0]，它会return 5.

我已经尝试了一个简单的 DFS，但是运行遇到了它多次运行相同点的问题，return 像 330 这样异常大的区域。

Answer 1

我真的想通了！

基本上它遵循仅向上、向下、向左和向右查找的 BFS 搜索。

关于寻找邻居的部分从 this answer 转到另一个问题。

def find_area(arr, x, y):
    queue = [(x,y)]
    visited = []
    w = len(arr[0])
    h = len(arr)
    area = 0
    while len(queue) != 0:
        curr = queue.pop(0)
        print(curr)
        x = curr[0]
        y = curr[1]
        if arr[curr[0]][curr[1]] == 0 and curr not in visited:
            area += 1
            visited.append(curr)
            neighbors = [(x+a[0], y+a[1]) 
                            for a in [(-1,0), (1,0), (0,-1), (0,1)] 
                            if ((0 <= x+a[0] < w) and (0 <= y+a[1] < h))]
            for i in neighbors:
                if i not in visited:
                    queue.append(i)
    return area

查找二维数组子空间的面积？

Finding area of subspace of 2d array?

python

arrays

breadth-first-search