javascript - JavaScript 二维数组中的算法

Question

您是 WeWork 等联合办公空间的所有者，并且您的办公楼是矩形的。 您的团队刚刚 build 了墙壁隔断，为初创公司创建迷你办公室。 该办公园区由 1(地板空间)和 0(墙壁)组成的二维数组表示。 该阵列上的每个点都是一英尺乘一英尺见方。 您需要计算办公室的数量。 单个办公室以墙壁为边界，并通过将楼层彼此相邻来构建， 水平和/或垂直。 水平或垂直相邻的两个 1 始终属于同一办公室。

函数 numOffices() 有一个参数:grid - 1 和 0 的 2D 网格/数组

在这个问题中，我们的输入格式如下:第一行是二维数组的行数。第二行是二维数组中的列数。输入的其余部分包含要处理的数据。

以下是原始输入的示例:

4 
5 
11110 
11010 
11000 
00000

Expected: Output returns the number of valid offices in the grid.

约束

Assume all four edges of the grid are all surrounded by walls. 
Assume that the bounds of the array are the following: 
The total amount of elements in the array: width x height <= 10^6

numOffices() 输入示例

4
5
11110
00000
00100
00011

示例输出

3

解决方案

There's 3 offices in this grid, one made of four 1s on the top left, 
one made of one 1 in the middle, and one made of two 1s in the bottom right.

编写一个函数 numOffices() 来解决这个问题。

Answer 1

找到下面的解决方案

/**
 * @param {character[][]} grid
 * @return {number}
 */

function numOffices(grid) {
    let result = 0;
    //Put your code here.
    let markIsland = function (grid, x, y, visited) {
        if (x < 0 || x > grid.length - 1 || y < 0 || y > grid[x].length - 1) {
            return;
        }
        if (visited[x][y] === true) {
            return;
        }
        visited[x][y] = true;
        if (grid[x][y] === '0') {
            return;
        }
        markIsland(grid, x - 1, y, visited);
        markIsland(grid, x + 1, y, visited);
        markIsland(grid, x, y - 1, visited);
        markIsland(grid, x, y + 1, visited);
    };

    let visited = [];
    for (let i = 0; i < grid.length; i++) {
        visited[i] = [];
    }
    for (let x = 0; x < grid.length; x++) {
        for (let y = 0; y < grid[x].length; y++) {
            if (!visited[x][y] && grid[x][y] === '1') {
                result++;
                markIsland(grid, x, y, visited);
            }
            visited[x][y] = true;
        }
    }
    return result;
};

let height = parseInt(readline());
let width = parseInt(readline());
let grid = [];
for (var i = 0; i < height; i++) {
    grid[i] = (readline() || "").split("");
}

print(numOffices(grid));

注意:复制和粘贴可能会让您通过测试，但通过查看脚本进行研究并可能对其进行改进将使您成为更好的开发人员