Функция DFS для поиска островков в двумерном массиве, возвращающих неправильные числа

Question

Я пытаюсь написать функцию, которая просматривает двумерный массив и возвращает «островки», кластеры любого числа, которое в принципе не равно 0.Упрощенно, ниже я объявил график, который должен возвращать 5 - поскольку есть 5 мест, где 1 сгруппированы / соло и окружены нулями.Кто-нибудь может увидеть, что не так с этим кодом?

    func numIslands(grid: [Array<Int>]) -> Int{
        if(grid == nil || grid.count == 0 || grid[0].count == 0){
            return 0
        }

        let m = grid.count
        let n = grid[0].count

        var count = 0
        for i in 0...m-1{
            for j in 0...n-1{
                if grid[i][j] >= 1 {
                    count += 1
                    merge(grid: grid, i: i, j: j);
                }
            }
        }
        return count;
    }

    func merge(grid: [Array<Int>], i: Int, j: Int){
        var grid = grid
        let m = grid.count
        let n = grid[0].count

        if(i < 0 || i >= m || j<0 || j >= n || grid[i][j] != 1){
            return
        }

        grid[i][j] = 0

        merge(grid: grid, i: i-1, j:j)
        merge(grid: grid, i: i+1, j:j)
        merge(grid: grid, i: i, j: j-1)
        merge(grid: grid, i: i, j: j+1)
    }

    var graph = [[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]]


    print(numIslands(grid: graph))
    //returns 10, should be 5

Answer 1

Основная ошибка здесь:

func merge(grid: [Array<Int>], i: Int, j: Int) {
    var grid = grid // Make a mutable copy

    // ... modify `grid` ...
}

Массивы типов значений в Swift.Функция merge() изменяет локальную переменную grid, но не переданный аргумент.Поэтому в основном цикле

var count = 0
for i in 0...m-1{
    for j in 0...n-1{
        if grid[i][j] >= 1 {
            count += 1
            merge(grid: grid, i: i, j: j);
        }
    }
}

сетка никогда не изменяется, и цикл просто подсчитывает количество >= 1 записей.

Вам нужен «параметр inout»

func merge(grid: inout [Array<Int>], i: Int, j: Int){
    let m = grid.count
    let n = grid[0].count

    if(i < 0 || i >= m || j<0 || j >= n || grid[i][j] != 1){
        return
    }

    grid[i][j] = 0

    merge(grid: &grid, i: i-1, j:j)
    merge(grid: &grid, i: i+1, j:j)
    merge(grid: &grid, i: i, j: j-1)
    merge(grid: &grid, i: i, j: j+1)
}

и только основная функция делает копию и передает ее функции в качестве аргумента inout с &:

var grid = grid
// ...
merge(grid: &grid, i: i, j: j);

С этим изменением результат будет 6(а не ожидаемое 5), поскольку merge() не объединяет диагональ соседей.Но теперь это легко исправить.