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

分值： 300分

题解： Java / Python / C++

题目描述

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

输入描述

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

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

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

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

输出描述

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

示例1

输入：451 0 0 0 11 1 1 1 11 0 1 1 01 1 1 1 1输出：[3,2,3]解释：满足条件且面积最大的正方形边界，其右下角的顶点为[3,2]，即行号为3，列号为2，其宽度为3，因此返回信息为[3,2,3]。