看没有人用前缀和,就来写一发。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前置知识
(地图数组为 aaa,前缀和数组为 sss)
si,j=ai,j+si−1,j+si,j−1−si−1,j−1s_{i,j}=a_{i,j}+s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1} si,j =ai,j +si−1,j +si,j−1 −si−1,j−1
以 (i,j)(i,j)(i,j) 为左上角、(k,l)(k,l)(k,l) 为右下角的区间和为:
sk,l−si−1,l−sk,j−1+si−1,j−1s_{k,l}-s_{i-1,l}-s_{k,j-1}+s_{i-1,j-1} sk,l −si−1,l −sk,j−1 +si−1,j−1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
遍历所有区间,以 (i,j)(i,j)(i,j) 为左上角、(k,l)(k,l)(k,l) 为右下角(i≤k, j≤li\le k,\ j\le li≤k, j≤l),判断区间内所有数的和是否为区间的面积,即 (k−i+1)×(l−j+1)(k-i+1)\times(l-j+1)(k−i+1)×(l−j+1)。若是,则区间内全部为 111,取最大值。
时间复杂度 O(n2m2)O(n^2m^2)O(n2m2)。
代码