原文链接: https://leetcode-cn.com/problems/max-black-square-lcci

英文原文

Imagine you have a square matrix, where each cell (pixel) is either black or white Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.

Return an array [r, c, size], where r, c are the row number and the column number of the subsquare's upper left corner respectively, and size is the side length of the subsquare. If there are more than one answers, return the one that has smallest r. If there are more than one answers that have the same r, return the one that has smallest c. If there's no answer, return an empty array.

Example 1:

Input:
[
   [1,0,1],
   [0,0,1],
   [0,0,1]
]
Output: [1,0,2]
Explanation: 0 represents black, and 1 represents white, bold elements in the input is the answer.

Example 2:

Input:
[
   [0,1,1],
   [1,0,1],
   [1,1,0]
]
Output: [0,0,1]

Note:

• matrix.length == matrix[0].length <= 200

中文题目

给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。

返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。

示例 1:

输入:
[
   [1,0,1],
   [0,0,1],
   [0,0,1]
]
输出: [1,0,2]
解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵

示例 2:

输入:
[
   [0,1,1],
   [1,0,1],
   [1,1,0]
]
输出: [0,0,1]

提示：

• matrix.length == matrix[0].length <= 200

通过代码

高赞题解

解题思路

动态规划，cnt[r][c][0/1]表示以坐标r,c为起点向左/右最多的连续黑色块的数量

代码

class Solution {
public:
    vector<int> findSquare(vector<vector<int>>& matrix) {
        vector<int> ans(3, 0);
        int n = matrix.size();
        if(n == 0) return {};
        if(n == 1){
            if(matrix[0][0] == 0)
                return {0, 0, 1};
            else
                return {};
        }
        //cnt[r][c][0/1],0右侧,1下侧
        vector<vector<vector<int>>> cnt(n, vector<vector<int>>(n, vector<int>(2)));
        for(int r = n-1; r >= 0; r--){
            for(int c = n-1; c >= 0; c--){
                if(matrix[r][c] == 1)
                    cnt[r][c][0] = cnt[r][c][1] = 0;
                else{
                    //统计cnt[r][c][0/1]
                    if(r < n-1) cnt[r][c][1] = cnt[r+1][c][1] + 1;
                    else cnt[r][c][1] = 1;

                    if(c < n-1) cnt[r][c][0] = cnt[r][c+1][0] + 1;
                    else cnt[r][c][0] = 1;
				   //更新当前最大子方阵
                    int len = min(cnt[r][c][0], cnt[r][c][1]);//最大的可能的边长
                    while(len >= ans[2]){//要答案r,c最小，所以带等号
                        if(cnt[r+len-1][c][0] >= len && cnt[r][c+len-1][1] >= len){
                            //可以构成长为len的方阵
                            ans = {r, c, len};
                            break;
                        }
                        len--;
                    }
                }
            }
        }
        return ans;
    }
};

统计信息

通过次数	提交次数	AC比率
4860	12870	37.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言