goden1723

面试题 17.23.最大黑方阵

1. 题目描述

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

标签 数组 动态规划 矩阵

2. 解题

首先要注意：是要求四条边为0即可，而不是整个正方形范围内全为0。

若有四个矩阵：

1. 从上面数，有几个连续的黑色区域
2. 从左边数，有几个连续的黑色区域
3. 从下面数，有几个连续的黑色区域
4. 从右边数，有几个连续的黑色区域

如：

[
   [1,0,1],
   [0,0,1],
   [0,0,1]
]

其三个矩阵分别为：

up:
[
   [0, 1, 0],
   [1, 2, 0],
   [2, 3, 0]
]

left:
[
   [0, 1, 0],
   [1, 2, 0],
   [1, 2, 0]
]

down:
[
   [0, 3, 0],
   [2, 2, 0],
   [1, 1, 0]
]

right:
[
   [0, 1, 0],
   [2, 1, 0],
   [2, 1, 0]
]

则对于每个位置， 若是黑色，首先找到其往下和往右延伸的最小黑色长度，再检查其延伸到的右下角是否可有效延伸到左上角。若能延伸到，则可确定这个位置的最大黑色方阵，若延伸不到，则减小其延伸长度，再次判断。