javascript - 岛屿数量 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 数组来检查是否该位置是否被访问。如果它被 for 循环或递归访问，则为 1，否则为 0。

它有一个错误

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

TypeError: Cannot read property 'length' of undefined

有人可以帮我指出我的错误吗？我整个上午都在试图找出我的解决方案出了什么问题。

此致。

标签： javascriptalgorithmdata-structures

Answer 1

在第 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);