求1和0矩阵中最大尺寸平方的Javascript算法

Question

你拥有一个像WeWork这样的合作空间，你的办公大楼是长方形的。您的团队刚刚创建了许多墙分区，为初创企业创建迷你办公室。你的办公室校园是由1s (地板空间)和0(墙壁)组成的2D数组表示的。这个阵列上的每个点是一个1英尺乘1英尺的正方形。在租给房客之前，你想为自己预订一间办公室。您希望在您的办公室中适合最大的长方形表，并且您将选择适合此表的office。桌子的两边将永远平行于办公楼的边界。你办公室里最大的桌子的面积是多少？

函数biggestTable()有一个参数：

网格:1和0的二维网格/数组

我们的一些模板的输入格式，我们已经为您处理了解析。如果我们不提供解析函数，则需要直接解析输入。在这个问题上，我们的输入格式如下：

第一行是2D数组中的行数，第二行是2D数组中的列数，其余的输入包含要处理的数据，这里是原始输入的一个示例：

4
5
11110
11010
11000
00000

期望输出返回网格中由1s构成的最大直角平行四边形的面积。假设网格被0(墙壁)包围。

约束假定数组的边界如下:数组中元素的总数:宽度x高度<= 10^6

示例

Example biggestTable() Input

grid: 
    [[1, 0, 1, 1, 1],
     [1, 0, 1, 1, 1],
     [1, 1, 1, 1, 1],
     [1, 0, 0, 1, 0]]
Example Output

9


/**
 * @param {character[][]} grid
 * @return {number}
 */
var biggestTable = function(grid) {
    // your code here

    return 0;
};

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

有谁能帮忙解决这个问题吗？

Answer 1

这个问题可以用一种逻辑的方式来处理，您可以循环遍历建筑物并检查表可以放置的潜在空间，然后返回找到的最大的表：

function biggestTable(grid) {
    const tableExist = (x, y, w, h) => {
        let exist = 1;
        for(let i = 0; i < w ; i++) {
            for(let j = 0; j < h ; j++) {
                exist &= grid[j + y] !== undefined && grid[j + y][i + x] == 1;
            }
        }
        return exist;
    };

    const biggestTableAt = (x, y) => {
        let max = 0;
        for(let w = 1; w <= grid[0].length; w++) {
            for(let h = 1; h <= grid.length; h++) {
                const table_size = w * h;
                if (tableExist(x, y, w, h) && table_size>max) {
                    max = table_size;
                }
            }
        }
        return max;
    };

    let max = 0;
    for(let x = 0; x < grid[0].length; x++) {
        for(let y= 0; y < grid.length; y++) {
            const table_size = biggestTableAt(x, y);
            if (table_size > max) {
                max = table_size;
            }
        }
    }
    return max;
}


const simple_grid = [
    [1, 0, 1, 1, 1],
    [1, 0, 1, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0]
];
console.log(biggestTable(simple_grid)); //returns 9
const big_grid = [
    [1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1],
    [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1],
    [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1],
];
console.log(biggestTable(big_grid)); // returns 18

接受的响应返回两个网格的9，因为它假设表是方形的，而不是问题中要求的矩形的。