JavaScript二维阵列中的算法

Question

你拥有一个像WeWork这样的合作空间，你的办公大楼是长方形的。您的团队刚刚建立了墙分区，为初创企业创建迷你办公室。这个办公室校园由1s (楼面空间)和0(墙壁)组成的二维数组表示。这个阵列上的每个点是一个1英尺乘1英尺的正方形。你需要计算出办公室的数量。一间办公室与墙壁接壤，建筑方式是将楼层彼此并排，水平和/或垂直。水平或垂直相邻的两个1s总是同一办公室的一部分。

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

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

下面是原始输入的一个示例：

4 
5 
11110 
11010 
11000 
00000

预期的

：输出返回网格中有效办公室的数量。

约束条件

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

​

注意:复制和粘贴可能会使您通过测试，但是仔细看一下脚本来学习并改进它将使您成为一个更好的开发人员。

Answer 2

下面是一个简单的解决问题的版本：

function numOffices(grid) {
  let result = 0;

  for (let x = 0; x < grid[0].length; x++) {
    if (grid[0][x] === 1 && grid[0][x - 1] !== 1) {
      result = result + 1;
    }
  }

  for (let y = 1; y < grid.length; y++) {
    for (let x = 0; x < grid[0].length; x++) {
      if (grid[y][x] === 1 && grid[y][x - 1] !== 1 && grid[y - 1][x] !== 1) {
        result = result + 1;
      }
    }
  }
  return result;
}

let grid = [
  [1, 1, 1, 1, 1],
  [1, 0, 0, 0, 1],
  [1, 0, 0, 0, 0],
  [1, 1, 1, 0, 1]
];

console.log(numOffices(grid));

Answer 3

我的解决方案

function numOffices(grid) {
    let result = 0;
    const gridHeight = grid.length;
    const gridLength = grid[0].length;

    for (var y = 0; y < gridHeight; y++) {
        for (var x = 0; x < gridLength; x++){
            const item = grid[y][x]

            if (item === 1){
                result = result + 1

                markRoom(null, x, y, grid)
            }
        }
    }

    console.log({result})
    return result;
};

function markRoom(from, x, y, grid){

    const item = grid[y][x]
    const gridHeight = grid.length;
    const gridLength = grid[0].length;

    if (item !== 1){
        return
    }

    grid[y][x] = -1

    if (from !== 'top' && y !== 0){
        markRoom('down', x, y-1, grid)
    }

    if (from !== 'right' && x!== gridLength -1){
        markRoom('left',x+1, y, grid)
    }

    if (from !== 'down' && y!== gridHeight-1){
        markRoom('up',x, y+1, grid)
    }

    if (from !== 'left' && x!== 0){
        markRoom('right',x-1, y, grid);
    }
}

const grid = [[1, 1, 0, 0, 0],
     [1, 1, 0, 0, 0],
     [0, 0, 1, 0, 0],
     [0, 0, 0, 1, 1]]

console.log(numOffices(grid))