C++刷leetcode（面试题 17.23. 最大黑方阵）【动态规划】

糖逗

do题目描述：

给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-black-square-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

vector<int> findSquare(vector<vector<int>>& matrix) {
        vector<int> res(3,0);
        //初始化
        int len = matrix.size();
        if(len == 0) return {};
        else if(len == 1){
            if(matrix[0][0] == 0) return {0,0,1};
            else return {}; 
        }
        vector<vector<vector<int> > > temp (len, vector<vector<int> > (len, vector<int> (2, 0)));//0是向下， 1向右
        for(int i = len -1; i >=0; i--){
            for(int j = len-1; j >= 0; j--){
                if(matrix[i][j] == 1) temp[i][j][1] = temp[i][j][0] = 0;
                else{
                   if(j+1 < len) temp[i][j][1] = temp[i][j+1][1] + 1;
                   else temp[i][j][1] = 1;

                   if(i+1 < len) temp[i][j][0] = temp[i+1][j][0] + 1;
                   else temp[i][j][0] = 1;

                   int len = min(temp[i][j][1], temp[i][j][0]);
                
                    while(len >= res[2]){//要答案r,c最小，所以带等号
                        if(temp[i+len - 1][j][1] >=len && temp[i][j+len-1][0] >= len){
                            res =  {i, j, len};
                            break;
                        }
                        len--;
                    }
                }
                
            }
        }
        return res;
    }

参考讲解：https://leetcode-cn.com/problems ... gui-hua-by-tmoonli/