平面灯阵中寻找最大正方形边界 - 华为机试真题题解-LMLPHP

题目描述

现在有一个二维数组来模拟一个平面灯阵,平面灯阵中每个位置灯处于点亮或熄灭,分别对应数组每个元素取值只能为1或0,现在需要找一个正方形边界,其每条边上的灯都是点亮(对应数组中元素的值为1)的,且该正方形面积最大。

输入描述

第一行为灯阵的高度(二维数组的行数)

第二行为灯阵的宽度(二维数组的列数)

紧接着为模拟平台灯阵的二维数组arr

1< arr.length <= 200
1< arr[0].length <= 200

输出描述

返回满足条件的面积最大正方形边界信息。返回信息[r,c,w],其中r,c分别代表方阵右下角的行号和列号,w代表正方形的宽度。如果存在多个满足条件的正方形,则返回r最小的,若r相同,返回c最小的正方形。

示例1

输入:
4
5
1 0 0 0 1
1 1 1 1 1
1 0 1 1 0
1 1 1 1 1

输出:
[3,2,3]

解释:
满足条件且面积最大的正方形边界,其右下角的顶点为[3,2],即行号为3,列号为2,其宽度为3,因此返回信息为[3,2,3]。

12-27 12:51