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

糖逗

do题目描述：

1. 给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
   
2. 
   
3. 返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入:
   
8. [
   
9.    [1,0,1],
   
10.    [0,0,1],
    
11.    [0,0,1]
    
12. ]
    
13. 输出: [1,0,2]
    
14. 解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
    
15. 示例 2:
    
16. 
    
17. 输入:
    
18. [
    
19.    [0,1,1],
    
20.    [1,0,1],
    
21.    [1,1,0]
    
22. ]
    
23. 输出: [0,0,1]
    
24. 提示：
    
25. 
    
26. matrix.length == matrix[0].length <= 200
    
27. 
    
28. 来源：力扣（LeetCode）
    
29. 链接：https://leetcode-cn.com/problems/max-black-square-lcci
    
30. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. vector<int> findSquare(vector<vector<int>>& matrix) {
   
2.         vector<int> res(3,0);
   
3.         //初始化
   
4.         int len = matrix.size();
   
5.         if(len == 0) return {};
   
6.         else if(len == 1){
   
7.             if(matrix[0][0] == 0) return {0,0,1};
   
8.             else return {};
   
9.         }
   
10.         vector<vector<vector<int> > > temp (len, vector<vector<int> > (len, vector<int> (2, 0)));//0是向下， 1向右
    
11.         for(int i = len -1; i >=0; i--){
    
12.             for(int j = len-1; j >= 0; j--){
    
13.                 if(matrix[i][j] == 1) temp[i][j][1] = temp[i][j][0] = 0;
    
14.                 else{
    
15.                    if(j+1 < len) temp[i][j][1] = temp[i][j+1][1] + 1;
    
16.                    else temp[i][j][1] = 1;
    
17. 
    
18.                    if(i+1 < len) temp[i][j][0] = temp[i+1][j][0] + 1;
    
19.                    else temp[i][j][0] = 1;
    
20. 
    
21.                    int len = min(temp[i][j][1], temp[i][j][0]);
    
22.                
    
23.                     while(len >= res[2]){//要答案r,c最小，所以带等号
    
24.                         if(temp[i+len - 1][j][1] >=len && temp[i][j+len-1][0] >= len){
    
25.                             res =  {i, j, len};
    
26.                             break;
    
27.                         }
    
28.                         len--;
    
29.                     }
    
30.                 }
    
31.                
    
32.             }
    
33.         }
    
34.         return res;
    
35.     }

复制代码

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