Количество островов LeetCode Q200

Question

Я пытаюсь сделать Q.200. Количество островов вопрос по Leetcode. Вопрос звучит так:

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

Example 1:

Input:
11110
11010
11000
00000

Output: 1


Example 2:

Input:
11000
11000
00100
00011

Output: 3

Ниже мое решение в JavaScript:

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    if (grid.length == 0) {
      return 0;
    }

    var count = 0;

    var z = new Array(grid[0].length).fill(0);
    var visit = new Array(grid.length);

    for (i = 0; i < visit.length; i++) {
        visit[i] = z;
    }

    function traverse(x, y, grid, visit, count) {
        var col = grid.length;
        var row = grid[0].length;
        if (x >= 0 && y >= 0 && x < row && y < col) {
            visit[x][y] = 1;
        } else {
            return;
        }
        if (grid[x][y] != 1) {
            return;
        } else {
            traverse(x + 1, y);
            traverse(x - 1, y);
            traverse(x, y + 1);
            traverse(x, y - 1);
            count++;
        }
    }

    for (i = 0; i < grid.length; i++) {
        for (j = 0; j < grid[0].length; j++) {
            if (visit[i][j] == 0) {
                traverse(i, j, grid, visit, count);
            } else {
                continue;
            }
        }
    }

    return count;
};

В основном я пытаюсь вызвать рекурсию, когда значение равно 1, и остановиться, когда пересечь некуда (конец острова), затем увеличить количество островов на 1. Я создал массив из 0 проверить, посещено ли местоположение или нет. Если его посещают либо для циклов, либо для рекурсии, он становится равным 1, в противном случае он равен 0.

Имеется ошибка

Line 20 in solution.js
         var col = grid.length;

TypeError: Cannot read property 'length' of undefined

Может ли кто-нибудь помочь мне указать на мою ошибку, пожалуйста? Я провел все утро, пытаясь выяснить, что не так с моим решением.

С уважением.

Answer 1

Вы должны проверить, посещался ли узел в начале функции перемещения.

if (x >= 0 && y >= 0 && x < row && y < col) {
    //////////////////////
    if (visit[x][y] == 1){
        return;
    }
    //////////////////////
    visit[x][y] = 1;
} else {
    return;
}

Answer 2

В строках 30-33 у вас есть следующее, что кажется неправильным:

        traverse(x + 1, y);
        traverse(x - 1, y);
        traverse(x, y + 1);
        traverse(x, y - 1);

Вместо этого вы можете добавить

        traverse(x + 1, y, grid, visit, count);
        traverse(x - 1, y, grid, visit, count);
        traverse(x, y + 1, grid, visit, count);
        traverse(x, y - 1, grid, visit, count);