Номер островного кода python - PullRequest
Новая
       19

Номер островного кода python

1 голос
/ 18 апреля 2020

Вопрос звучит следующим образом: Учитывая двумерную сеточную карту «1 (земля) и» 0 (вода), подсчитайте количество островов. Остров окружен водой и образован соединением соседних земель горизонтально или вертикально. Можно предположить, что все четыре ребра сетки окружены водой. 

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # use dfs / replace the island's elements with a sign "."
        a = len(grid)
        b = len(grid[0])
        num = 0


        for i in range(0 , a-1):
            for j in range(0 , b-1):
                if grid[i][j] == '1':
                    num += 1
                    self.dfs(grid , i , j)

        return num

    def dfs(self, grid , x , y):

        if x < 0 or y < 0 or x >= len(grid[0]) or y >= len(grid) or grid[x][y] == '0' or grid[x][y] == ".": # if out of boundary
            return

        grid[x][y] = "."        
        # if 1's has only one neighbor

        self.dfs(grid , x-1 , y)   # check 4 edges of water
        self.dfs(grid, x+1 , y)
        self.dfs(grid , x , y+1)
        self.dfs(grid , x , y- 1)

Этот код работает только для этого вывода: [["1", "1", "1", "1", "0"], [ "1", "1", "0", "1", "0"], [ "1", "1", "0", "0", "0"], [ «0», «0», «0», «0», «0»]]

Однако для этого вывода это не работает: [["1", "1", "0" , "0", "0"], [ "1", "1", "0", "0", "0"], [ "0", "0", "1", "0",» 0 "], [" 0 "," 0 "," 0 "," 1 "," 1 "]]

Я пытаюсь использовать метод dfs. Таким образом, если x находится в массиве, функция dfs проверит соседние элементы с 4-х сторон, независимо от того, является ли это «1» или нет, если это «1», то он заменяется на «.». в противном случае, если элемент равен «0», рекурсивная l oop останавливается. Как только все рекурсивные l oop останавливаются для всех возможных комбинаций, счет увеличивается на 1. Затем программа запускается, чтобы найти другой «X».

Однако программа не работает должным образом. Поэтому, может ли кто-нибудь помочь мне найти проблемы в этом коде?

...