平面灯阵中寻找最大正方形边界 - 华为机试真题题解

分值： 300分

题解： Java / Python / C++

题目描述

现在有一个二维数组来模拟一个平面灯阵，平面灯阵中每个位置灯处于点亮或熄灭，分别对应数组每个元素取值只能为1或0，现在需要找一个正方形边界，其每条边上的灯都是点亮(对应数组中元素的值为1)的，且该正方形面积最大。

输入描述

第一行为灯阵的高度(二维数组的行数)

第二行为灯阵的宽度(二维数组的列数)

紧接着为模拟平台灯阵的二维数组arr

1< arr.length <= 200 1< arr[0].length <= 200

输出描述

返回满足条件的面积最大正方形边界信息。返回信息[r,c,w],其中r,c分别代表方阵右下角的行号和列号，w代表正方形的宽度。如果存在多个满足条件的正方形，则返回r最小的，若r相同，返回c最小的正方形。

示例1

输入：
4
5
1 0 0 0 1
1 1 1 1 1
1 0 1 1 0
1 1 1 1 1

输出：
[3,2,3]

解释：
满足条件且面积最大的正方形边界，其右下角的顶点为[3,2]，即行号为3，列号为2，其宽度为3，因此返回信息为[3,2,3]。

示例2

输入：
3
3
1 0 0
0 1 0
0 0 1

输出：
[0,0,1]

解释：
满足条件且面积最大的正方形边界有三个。即为[0,0,1]、[1,1,1]、[2,2,1],根据要求，如果满足条件有多个，则返r最小，即为 [0,0,1]。

题解

动态规划的题目

解题思路

首先，我们需要计算每个位置的左侧和上侧连续为1的数量，以便在后续判断正方形边界时使用。（在代码实现中使用 row_psum 和 col_psum 来实现）

然后，我们遍历二维数组，对每个点 (r, c)，检查以该点为右下角的正方形边界，看是否满足条件。

最终，找到满足条件的最大正方形边界，返回其右下角的行号、列号和边长。

Java

import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    // 检查以（r,c）为正方形，宽度为 w 的正方形边界的灯是否都是点亮的
    static boolean check(int[][] row_psum, int[][] col_psum, int r, int c, int w) {
        // 下，右边检查
        if (row_psum[r][c] < w || col_psum[r][c] < w) return false;

        // 左、上边检查
        if (col_psum[r][c - w + 1] < w || row_psum[r - w + 1][c] < w) return false;

        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int h = scanner.nextInt();
        int w = scanner.nextInt();

        int[][] g = new int[h][w];
        for (int r = 0; r < h; r++) {
            for (int c = 0; c < w; c++) {
                g[r][c] = scanner.nextInt();
            }
        }

        // row_psum[r][c] 表示 （r,c） 左侧连续 1 的数量
        int[][] row_psum = new int[h][w];
        // col_psum[r][c] 表示 （r,c） 上侧连续 1 的数量
        int[][] col_psum = new int[h][w];

        for (int r = 0; r < h; r++) {
            for (int c = 0; c < w; c++) {
                if (g[r][c] == 0) continue;

                row_psum[r][c] = (c > 0 ? row_psum[r][c - 1] : 0) + 1;
                col_psum[r][c] = (r > 0 ? col_psum[r - 1][c] : 0) + 1;
            }
        }

        // [r, c, w]
        int[] result = new int[3];

        for (int r = 0; r < h; r++) {
            for (int c = 0; c < w; c++) {
                if (g[r][c] == 0) continue;

                for (int width = Math.min(r