中级编程通关练习题 #8 – 矩阵区域最大值

给定一个 MxN 的矩阵,里面的数值都是 1 和 0,一个有效区域是数值为 1 的位置上下左右连接而成。矩阵内部可能有多个有效区域,请找出区域最大的那一个。譬如下面的图案代表一个 12 x 7 的矩阵,黑色格子代表 0,黄色格子代表 1,矩阵里面总共有五个有效区域,最大的一个是8(八个黄色格子连接在一起)。

max inner area

输入样例:

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单元格。
  • 搜索到的有效区域数值保存到一个列表中,最后提取最大值即可。