给定[NxM]由0和1组成的矩阵.找到此矩阵中没有1(每个单元格为0)的方框数.固定方框的框架是一组单元,它们中的每一个是最左边,最右边,最顶部或最底部的单元之一.因此,边长为1的方框包含1个单元,边长2包含4个,边长3-8个单元,边长4-12个单元.
大小为4的示例框架是:
0000
0 0
0 0
0000
我们需要计算仅由0组成的方框数.
示例Let N=3和M=4和矩阵为:
0100
0100
0000
然后答案是12,因为有10个一个大小的帧和2个两个大小的帧.
主要问题是N,M可以达到1 ? N,M ? 2000.所以O(N^2)方法是必需的.