最大的以 1 为边界的正方形

[louzhedong]

习题

出处 LeetCode 算法第5041题

给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

示例 1：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9

示例 2：

输入：grid = [[1,1,0,0]]
输出：1

提示：

• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] 为 0 或 1

思路

思路一：从最大的正方形开始，判断正方形的四边是否都是1，如果不是，逐步将正方形缩小，并在整个大矩阵中从左上往右下移动，遇到四边都为1的情况，该正方形的大小则为结果

思路二：动态规划，类似题目都可以用动态规划解决

解答

// 思路一：遍历法
var largest1BorderedSquare = function (grid) {
  var rows = grid.length, cols = grid[0].length;
  var l = Math.min(rows, cols);
  for (; l > 0; l--) {
    for (var i = 0; i < rows; i++) {
      if (i + l - 1 >= rows) break;
      for (var j = 0; j < cols; j++) {
        if (j + l - 1 >= cols) break;
        for (var n = 0; n < l; n++) {
          // 判断圈定的正方形的四边是否都是1
          if (grid[i][j + n] != 1) break;
          if (grid[i + l - 1][j + n] != 1) break;
          if (grid[i + n][j] != 1) break;
          if (grid[i + n][j + l - 1] != 1) break;
        }
        if (n == l) return l * l;
      }
    }
  }
  return 0;
};
// 思路二，待补充