2023.12.20-秋招-第三题-平面灯阵中寻找最大正方形边界

TaZi SU @ 9 months ago

题面描述：

在这个问题中，给定一个二维数组表示黑白棋盘，黑棋用1表示，白棋用0表示。目标是找到一个最大的正方形，其边界由黑棋（1）组成，并返回该正方形的右下角坐标及其宽度。如果有多个满足条件的正方形，则返回右下角行号最小的，若行号相同则返回列号最小的。输入包括棋盘的行数和列数，以及棋盘的具体内容，输出为一个列表，包含满足条件的最大正方形的信息。

思路：动态规划/前缀和

原题来自于LeetCode 1139. 最大的以 1 为边界的正方形

我们只需要在此基础上找到这个正方形的右下角即可。

由于题目数据大为 $200$ , 所以 $O(n^3)$ 可过。那么就有非常多的做法(参考leetcode题解)。*下面给出的是一种前缀和差分的做法:*

枚举右下角，再枚举对角线。这样我们就用 $O(n^3)$ 的复杂度枚举出了所有可能的正方形。

然后我们只需要差分求这个正方形减去内部小正方形的和。这样就得到了边界上的值的和。看他是不是(边长 - 1) * 4 即可。

题解

在给定的黑白棋盘中，我们需要找到一个最大的正方形，其边界上都是黑棋（值为1）。由于棋盘的大小限制为200x200，因此可以采用 $O(n^3)$ 的复杂度进行求解。以下是利用前缀和和差分的方法来解决此问题的思路：

前缀和计算：使用一个额外的数组 dp 来存储到当前位置的黑棋（1）的累积和。这样可以快速计算任意子矩形的黑棋总数。
枚举正方形的右下角：我们从棋盘的右下角开始枚举每个可能的正方形的右下角位置，接着枚举可能的正方形的边长。
计算边界和：通过差分的方式，我们可以快速计算出正方形的边界值的和，并与理论值比较，判断是否为合法的正方形。
更新结果：当找到一个合法的正方形时，更新当前最大正方形的信息，如果存在多个满足条件的正方形，则根据题目要求选择合适的返回值。

时间复杂度

$O(n^3)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

int dp[205][205]; // 前缀和数组

class Solution {
public:
    // 计算区域 (x, y) 到 (a, b) 的和
    inline int ask(int x, int y, int a, int b) {
        return dp[a][b] - dp[a][y - 1] - dp[x - 1][b] + dp[x - 1][y - 1];
    }

    vector<int> largest1BorderedSquare(vector<vector<int>>& a) {
        int n = a.size(), m = a[0].size(); // 行数和列数
        int sum = 0; // 黑棋的总数
        int i, j, k;

        // 计算前缀和
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; j++) {
                int v = a[i - 1][j - 1]; // 当前元素的值
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + v; 
                sum += v; // 累计黑棋的总数
            }
        }

        // 如果没有黑棋，返回 [0, 0, 0]
        if (!sum) return {0, 0, 0};

        int ans = 1, len;
        int r = 1e9, c = 1e9; // 初始化返回值

        // 从右下角开始枚举
        for (i = n; i >= 1; i--) {
            for (j = m; j >= 1; j--) {
                len = min(i, j); // 当前正方形的最大边长

                // 枚举边长
                for (k = ans; k <= len; k++) {
                    // 计算边界的和，并与理论值比较
                    if (ask(i - k + 1, j - k + 1, i, j) - ask(i - k + 2, j - k + 2, i - 1, j - 1) == 4 * (k - 1)) {
                        // 更新最大正方形的信息
                        if (ans < k) {
                            ans = k; // 更新边长
                            r = i; // 更新右下角行号
                            c = j; // 更新右下角列号
                        } else if (ans == k) {
                            if (i < r) { // 优先选择行号最小的
                                r = i;
                                c = j;
                            } else if (i == r && j < c) { // 行号相同，选择列号最小的
                                c = j;
                            }
                        }
                    }
                }
            }
        }
        return {r, c, ans}; // 返回右下角坐标和边长
    }
};

int main() {
    int n, m;
    cin >> n >> m; // 输入行数和列数
    Solution sol;
    vector<vector<int>> a(n, vector<int>(m)); // 创建棋盘数组
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j]; // 输入棋盘数据
        }
    }
    vector<int> res = sol.largest1BorderedSquare(a); // 计算结果
    cout << "[" << res[0] - 1 << "," << res[1] - 1 << "," << res[2] << "]" << endl; // 输出结果
    return 0;
}

python代码

def ask(x, y, a, b, dp):
    # 计算矩形 (x, y) 到 (a, b) 的和
    return dp[a][b] - dp[a][y - 1] - dp[x - 1][b] + dp[x - 1][y - 1]

def largest1BorderedSquare(a):
    n = len(a)  # 获取行数
    m = len(a[0])  # 获取列数
    # 初始化前缀和数组，大小为 (n + 1) x (m + 1)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    sum = 0  # 黑棋的总数

    # 计算前缀和
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            v = a[i - 1][j - 1]  # 当前元素的值
            # 更新前缀和
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + v
            sum += v  # 累计黑棋的总数

    # 如果没有黑棋，返回 [0, 0, 0]
    if sum == 0:
        return [0, 0, 0]

    ans = 1  # 当前找到的最大正方形的边长
    r = float('inf')  # 右下角的行号初始化为正无穷
    c = float('inf')  # 右下角的列号初始化为正无穷

    # 从右下角开始枚举每个可能的正方形的右下角
    for i in range(n, 0, -1):
        for j in range(m, 0, -1):
            length = min(i, j)  # 当前正方形的最大边长

            # 枚举边长
            for k in range(ans, length + 1):
                # 计算边界的和，并与理论值比较
                if ask(i - k + 1, j - k + 1, i, j, dp) - ask(i - k + 2, j - k + 2, i - 1, j - 1, dp) == 4 * (k - 1):
                    # 更新最大正方形的信息
                    if ans < k:
                        ans = k  # 更新边长
                        r = i  # 更新右下角行号
                        c = j  # 更新右下角列号
                    elif ans == k:
                        # 优先选择行号最小的
                        if i < r:
                            r = i
                            c = j
                        elif i == r and j < c:  # 行号相同，选择列号最小的
                            c = j

    # 返回右下角坐标和边长
    return [r, c, ans]

# 读取输入
n = int(input())  # 输入行数
m = int(input())  # 输入列数
a = []  # 初始化棋盘数组

# 读取棋盘数据
for _ in range(n):
    a.append(list(map(int, input().split())))

# 计算最大正方形信息
res = largest1BorderedSquare(a)

# 输出结果，返回值减去1以符合题目要求（0-indexed）
print("[{},{},{}]".format(res[0] - 1, res[1] - 1, res[2]))

Java代码

import java.util.*;

public class Main {
    private static int[][] dp; // 前缀和数组，用于存储到当前位置的黑棋（1）的累积和

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 输入棋盘的行数
        int m = scanner.nextInt(); // 输入棋盘的列数
        int[][] a = new int[n][m]; // 初始化棋盘数组
        // 读取棋盘数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = scanner.nextInt(); // 读取每个位置的值
            }
        }
        // 计算最大正方形并输出结果
        int[] res = largest1BorderedSquare(a);
        System.out.println("[" + (res[0] - 1) + "," + (res[1] - 1) + "," + res[2] + "]"); // 输出结果，返回值减去1以符合题目要求
    }

    public static int[] largest1BorderedSquare(int[][] a) {
        int n = a.length, m = a[0].length, sum = 0; // 获取行数、列数和黑棋总数
        dp = new int[n + 1][m + 1]; // 初始化前缀和数组，大小为 (n + 1) x (m + 1)
        
        // 计算前缀和
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int v = a[i - 1][j - 1]; // 当前元素的值
                // 更新前缀和数组
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + v;
                sum += v; // 累计黑棋（1）的总数
            }
        }

        // 如果没有黑棋，直接返回 [0, 0, 0]
        if (sum == 0) return new int[]{0, 0, 0};

        int ans = 1; // 当前找到的最大正方形的边长
        int len, r = Integer.MAX_VALUE, c = Integer.MAX_VALUE; // 初始化右下角行列号为正无穷

        // 从右下角开始枚举每个可能的正方形的右下角
        for (int i = n; i >= 1; i--) {
            for (int j = m; j >= 1; j--) {
                len = Math.min(i, j); // 当前正方形的最大边长

                // 枚举边长
                for (int k = ans; k <= len; k++) {
                    // 计算边界的和，并与理论值比较
                    if (ask(i - k + 1, j - k + 1, i, j) - ask(i - k + 2, j - k + 2, i - 1, j - 1) == 4 * (k - 1)) {
                        // 更新最大正方形的信息
                        if (ans < k) {
                            ans = k; // 更新边长
                            r = i; // 更新右下角行号
                            c = j; // 更新右下角列号
                        } else if (ans == k) {
                            // 优先选择行号最小的
                            if (i < r) {
                                r = i; // 更新行号
                                c = j; // 更新列号
                            } else if (i == r) {
                                if (j < c) {
                                    c = j; // 更新列号
                                }
                            }
                        }
                    }
                }
            }
        }
        // 返回右下角坐标和边长
        return new int[]{r, c, ans};
    }

    // 计算区域 (x, y) 到 (a, b) 的和
    private static int ask(int x, int y, int a, int b) {
        return dp[a][b] - dp[a][y - 1] - dp[x - 1][b] + dp[x - 1][y - 1];
    }
}

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

# Submissions

135

Accepted

Uploaded By

TaZi

1 solutions

题面描述：

思路：动态规划/前缀和

题解

时间复杂度

代码

Information

Status

Development

Support