C++刷leetcode（面试题 17.23. 最大黑方阵）【动态规划】
do题目描述：给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
返回一个数组 ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。
示例 1:
输入:
[
,
,
]
输出:
解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
示例 2:
输入:
[
,
,
]
输出:
提示：
matrix.length == matrix.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) 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 == 1) temp = temp = 0;
else{
if(j+1 < len) temp = temp + 1;
else temp = 1;
if(i+1 < len) temp = temp + 1;
else temp = 1;
int len = min(temp, temp);
while(len >= res){//要答案r,c最小，所以带等号
if(temp >=len && temp >= len){
res ={i, j, len};
break;
}
len--;
}
}
}
}
return res;
}
参考讲解：https://leetcode-cn.com/problems/max-black-square-lcci/solution/c-dong-tai-gui-hua-by-tmoonli/
页:
[1]