讨论/面试考题/一道求矩阵中最大面积的笔试题,求大神帮助!/
一道求矩阵中最大面积的笔试题,求大神帮助!

在 10x10 的矩阵中有若干个相连区域。相连区域由上下左右数值为 1 的相邻方格组成(斜对角不属于相邻)。求给出矩阵中最大的相连区域面积,每个方格面积均为 1。

示例:
image.png

该情况下有 4 个相连区域,绿色区域面积为 2,蓝色区域面积为 8,红色区域面积为 8,黄色区域面积为 19。因此,最大面积为 19。

输入:
由 0、1 和「空格」组成的字符串

0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0

备注:
矩阵中至少存在一个相连区域

共 6 个回复

找了一会 LeetCode 695题 岛屿的最大面积

5

按行切割,每行用单调栈结构对所以元素找左右比起小的的位置,底乘高求面积,底是左右比其小的长度,高是连续1的长度

从任意一个没有访问过的1开始深度或者广度优先。另外用一个数组标记哪些访问过。可以得到结果。

广搜/深搜,记得加visit标识,然后求出每个岛屿,找最大面积

广度遍历每一个是1的位置,同时把和它一起所组成的这个岛屿上的每一个位置都做一个标记,下次如果又找到这个岛屿就不要再遍历了。

row * col + col当值,并查集,再统计一下最多的。