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

分值： 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(row_psum[r][c], col_psum[r][c]); width > result[2]; width--) {
                    if (check(row_psum, col_psum, r, c, width)) {
                        result[0] = r;
                        result[1] = c;
                        result[2] = width;
                        break;
                    }
                }
            }
        }

        System.out.println("[" + result[0] + "," + result[1] + "," + result[2] + "]");
    }
}

Python

def check(row_psum, col_psum, r, c, w):
    # 下，右边检查
    if row_psum[r][c] < w or col_psum[r][c] < w:
        return False

    # 左、上边检查
    if col_psum[r][c - w + 1] < w or row_psum[r - w + 1][c] < w:
        return False

    return True


def main():
    H, W = int(input()), int(input())
    g = [list(map(int, input().split())) for _ in range(H)]

    # row_psum[r][c] 表示 （r,c） 左侧连续 1 的数量
    row_psum = [[0] * W for _ in range(H)]
    # col_psum[r][c] 表示 （r,c） 上侧连续 1 的数量
    col_psum = [[0] * W for _ in range(H)]

    for r in range(H):
        for c in range(W):
            if g[r][c] == 0:
                continue

            row_psum[r][c] = row_psum[r][c - 1] + 1 if c > 0 else 1
            col_psum[r][c] = col_psum[r - 1][c] + 1 if r > 0 else 1

    # [r, c, w]
    result = [0, 0, 0]

    for r in range(H):
        for c in range(W):
            if g[r][c] == 0:
                continue

            width = min(row_psum[r][c], col_psum[r][c])
            for w in range(width, result[2], -1):
                if check(row_psum, col_psum, r, c, w):
                    result = [r, c, w]
                    break

    print(result)


if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 检查以（r,c）为正方形，宽度为 W 的正方形边界的灯是否都是点亮的
bool check(vector<vector<int>>& row_psum,  vector<vector<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;
}

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<int>> g(H, vector<int>(W));
    for(int r=0; r<H; r++) {
        for(int c=0; c<W; c++) {
            cin >> g[r][c];
        }
    }

    // row_psum[r][c] 表示 （r,c） 左侧连续 1 的数量
    vector<vector<int>> row_psum(H, vector<int>(W));
    // col_psum[r][c] 表示 （r,c） 上侧连续 1 的数量
    vector<vector<int>> col_psum(H, vector<int>(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]
    vector<int> result(3);

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

            for(int w = min(row_psum[r][c], col_psum[r][c]); w > result[2]; w--) {
                if(check(row_psum, col_psum, r, c, w)) {
                    result[0] = r;
                    result[1] = c;
                    result[2] = w;
                    break;
                }
            }
        }
    }

    cout << "[" << result[0] << "," << result[1] << "," << result[2] << "]" << endl;


    return 0;
}

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。