寻找岛屿的 DFS Python

Question

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

所以我想找到所有带有 1 的岛屿，以及它们是否相连（相邻的单元格）。所以我想 return 找到的岛屿数量。

这是我目前所知道的。

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 的个数。
您应该通过将其更改为 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

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

寻找岛屿的 DFS Python

DFS for finding Island Python

python

depth-first-search