用于查找孤岛Python的DFS

Question

我尝试这种方法已经有一段时间了，但岛屿数一直是0。我不太清楚我在这里做错了什么。随着我开始越来越多地学习python，我可能会错过一些容易发现的东西

所以我想找到所有岛，其中有一个1，如果它们是连接的（相邻单元）。所以我想返回发现的岛屿数量的计数

这是我到目前为止所拥有的

def valid_direction(A, r, c):
    row = len(A)
    col = len(A[0])
    if r < 0 or c < 0 or r >= row or c >= col:
        return False
    else:
        return True

def dfs(A, r, c):
    A[r][c] = '1'
    # Up down left and right
    directions = [(0,1), 
                  (0,-1), 
                  (-1,0),
                  (1,0)] 
    for d in directions:
        nr = r +d[0]
        nc = c + d[1]
        if valid_direction(A, nr, nc) and A[nr][nc] == '1':
            dfs(A, nr, nc)


def solution(A):
    if not A:
        return -1

    row = len(A)
    col = len(A[0])
    results = 0
    for i in range(row):
        for j in range(col):
            if A[i][j] == '1':
                dfs(A, i, j)
                results +=1
    return results

下面是我正在使用的两个阵列

A1 = [[1,1,1,1,0],
      [1,1,0,1,0],
      [1,1,0,0,0,],
      [0,0,0,0,0]]

A2 = [[1,1,0,0,0],
      [1,1,0,0,0],
      [0,0,1,0,0],
      [0,0,0,1,1]]

Answer 1

你犯了一个简单的错误。您的数组是整数数组，而不是字符数组。
A[r][c] = '1'和A[nr][nc] == '1'和if A[i][j] == '1'
应该是
A[r][c] = 1和A[nr][nc] == 1和if A[i][j] == 1
我不确定这之后它是否能正确解决问题，但这是当前的错误

---

您当前的代码只计算1的数量。
您应该通过将1更改为2来检查1是否被访问。
此外，您不必在每次调用dfs时都启动方向，您只需将其置于函数之外即可

directions = [(0,1), 
              (0,-1), 
              (-1,0),
              (1,0)]

def valid_direction(A, r, c):
    row = len(A)
    col = len(A[0])
    if r < 0 or c < 0 or r >= row or c >= col:
        return False
    else:
        return True

def dfs(A, r, c):
    A[r][c] = 2
    # Up down left and right 
    for d in directions:
        nr = r +d[0]
        nc = c + d[1]
        if valid_direction(A, nr, nc) and A[nr][nc] == 1:
            dfs(A, nr, nc)


def solution(A):
    if not A:
        return -1

    row = len(A)
    col = len(A[0])
    results = 0
    for i in range(row):
        for j in range(col):
            if A[i][j] == 1:
                dfs(A, i, j)
                results +=1
    return results

我不完全确定你想解决什么问题，但我认为正确的代码是这样的