给定一个 MxN 的矩阵,里面的数值都是 1 和 0,一个有效区域是数值为 1 的位置上下左右连接而成。矩阵内部可能有多个有效区域,请找出区域最大的那一个。譬如下面的图案代表一个 12 x 7 的矩阵,黑色格子代表 0,黄色格子代表 1,矩阵里面总共有五个有效区域,最大的一个是8(八个黄色格子连接在一起)。
输入样例:
matrix = [
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1],
[1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1]
]
输出样例:
10
上面的输入样例中,最大的有效区域就是连接在一起的红色数值1,总共是10个。
算法思路:
- 循环矩阵的每一个单元格,然后采用递归函数来搜索它的上下左右四个方向。
- 需要使用一个缓存元组来记录已经访问过的数值为1单元格。
- 搜索到的有效区域数值保存到一个列表中,最后提取最大值即可。