一、解题思路分析

本题的核心是在给定的 N×M 矩阵中，找出满足特定条件（一条对角线上方格都有奖品，其他方格都没有奖品）的正方形区域，并且该区域内奖品数量最多。

暴力枚举法：

这是解决此类问题比较直接的思路。

枚举正方形的左上角坐标：通过两层循环遍历矩阵的每一个方格，将每个方格作为可能的正方形区域的左上角。这样做的原因是，只要确定了正方形的左上角，再结合边长，就能确定整个正方形区域在矩阵中的位置。

枚举正方形的边长：对于每一个确定的左上角坐标，从边长为 1 开始，逐渐增大边长进行尝试，直到边长不能再增大（受限于矩阵边界，即边长不能超过从当前左上角位置到矩阵右边界和下边界的最小距离）。

检查正方形区域是否满足条件：当确定了左上角坐标和边长后，需要检查这个正方形区域是否满足题目要求。即检查其中一条对角线上的方格是否都有奖品（值为 1 ），同时检查除这条对角线外的其他方格是否都没有奖品（值为 0 ）。如果满足条件，说明找到了一个符合要求的正方形区域，记录下其边长（因为奖品数量等于边长的平方），并与之前记录的最大边长进行比较，取较大值。

具体检查逻辑：

对角线检查：对于选定的正方形区域，遍历其一条对角线（比如主对角线）上的每个方格，检查方格的值是否为 1 。如果有一个方格的值为 0 ，则该正方形区域不满足条件。

非对角线检查：在确认对角线满足条件后，遍历正方形区域内除对角线外的其他方格，检查这些方格的值是否为 0 。只要有一个方格的值为 1 ，就说明该正方形区域不符合要求。

关键代码：

CPP

int res = 0;
// 枚举正方形的左上角坐标
for (int i = 0; i < n; i++) {
   for (int j = 0; j < m; j++) {
       // 枚举正方形的边长
       for (int len = 1; len <= min(n - i, m - j); len++) {
           if (check(i, j, len)) {
               res = max(res, len);
           }
       }
   }
}

题解：B4293 [蓝桥杯青少年组省赛 2022] 奖品

文章操作