搜索矩阵中数字为偶数的最大矩形 [英] Searching for largest rectangle with even count of numbers in matrix
问题描述
例如，我有一个a * b数字矩阵(从0到9)
I have an a*b matrix of numbers (from 0 to 9), for example
[[1,2,3],
[4,5,6],
[7,6,5]]
我想找到最大的矩形，每个数字的个数在哪里(在本示例中，结果将是)
And I want to find the largest rectagle, where is count of each number even (in this example, the result will be)
[[5,6],
[6,5]] -- numbers 5 an 6 are here 2 times
在这里，无论如何，如何在n * log(n)或更佳的时间找到它，其中n是矩阵中的项目计数(n = a * b)? (如果该Rectagle不存在，则结果将为空集)
Is here any way, how to find it in n*log(n) or better time where n is count of items in matrix (n = a*b)? (If that rectagle doesn't exist, the result will be an empty set)
谢谢
推荐答案
您可以在O(N)时间(其中N是像元数)中创建第二个矩阵，然后将其用于检查特定矩形在O(1)时间中的每个数字都有偶数.但是，候选矩形的数量与N 2 有关，因此最坏的情况是O(N 2 ).您可以使用动态编程，并从较小的矩形扩展到较大的矩形，但是由于我们正在寻找最大的矩形，因此对于一般情况而言可能适得其反. (更新:我怀疑最坏的情况是没有有效矩形的矩阵对于大于63x63的正方形输入是不可能的；请参见下文.)
You can create a second matrix in O(N) time (where N is the number of cells), which can then be used to check whether a certain rectangle has an even number of every digit in O(1) time. The number of candidate rectangles is however related to N2, so the worst case will be O(N2). You could use dynamic programming and build up from smaller rectangles to larger ones, but because we're looking for the largest rectangle, that may be counter-productive for the average case. (Update: I suspect that the worst case, a matrix with no valid rectangles, is impossible for square input larger than 63x63; see below.)
我们将创建另一个包含10位整数的矩阵，其中每个位指示从该位置到右下角的矩形中某个数字是偶数还是奇数.我们将从右下角开始，一直到左上角，使用已经添加的相邻整数来计算新的整数:
We'll create a second matrix holding 10-bit integers, where each bit indicates whether there is an even or odd number of a certain digit in the rectangle from that position to the bottom-right corner. We'll start with the bottom-right corner, and work our way up to the top-left corner, using the adjacent integers we've already added to calculate the new ones:
2 8 6 5 ---------- ---------- ---------- ----------
3 2 1 4 ---------- ---------- ---------- ----------
1 3 2 5 ---------- ---------- ---------- ----------
7 2 0 9 ---------- ---------- ---------- 1000000000
右下角的整数设置有第9位，因为该位置的值为9.然后我们计算两个相邻的边缘位置:
The integer for the bottom-right corner has its 9th bit set, because the value at that position is 9. Then we calculate the two adjacent edge positions:
2 8 6 5 ---------- ---------- ---------- ----------
3 2 1 4 ---------- ---------- ---------- ----------
1 3 2 5 ---------- ---------- ---------- 1000100000
7 2 0 9 ---------- ---------- 1000000001 1000000000
通常，我们可以通过以下方式来计算位模式:设置与该位置的值相对应的位，然后将该模式与当前位置的右，下和右下角的三个相邻模式进行异或: /p>
In general, we can calculate the bit pattern by setting the bit that corresponds to the position's value, and xor-ing this pattern with the three adjacent patterns to the right, bottom, and bottom-right of the current position:
position (2,2): 0000000100 (value = 2)
position (3,2): 1000100000
position (2,3): 1000000001
position (3,3): 1000000000
XOR: 1000100101
2 8 6 5 ---------- ---------- ---------- ----------
3 2 1 4 ---------- ---------- ---------- ----------
1 3 2 5 ---------- ---------- 1000100101 1000100000
7 2 0 9 ---------- ---------- 1000000001 1000000000
对于沿右边缘和底边缘的位置，我们仅对当前位置下方或右侧的一个相邻图案进行异或运算.最终，我们得到了这个矩阵:
For positions along the right and bottom edges, we only xor with one adjacent pattern, under or to the right of the current position. Eventually we get this matrix:
2 8 6 5 1111010001 1101011111 1001010111 1000010000
3 2 1 4 1010110101 1000111111 1000110111 1000110000
1 3 2 5 1010101011 1000101001 1000100101 1000100000
7 2 0 9 1010000101 1000000101 1000000001 1000000000
有了这个矩阵，我们现在可以通过将其左上角的图案与其下方，右侧和底部的图案异或，来检查任何矩形的每个位数是否具有偶数.它:
With this matrix, we can now check whether any rectangle has an even number of every digit, by xor-ing its top-left pattern with the pattern under it, to the right of it, and to the bottom-right of it:
- - - - ---------- ---------- ---------- ----------
3 2 1 - 1010110101 ---------- ---------- 1000110000
1 3 2 - ---------- ---------- ---------- ----------
- - - - 1010000101 ---------- ---------- 1000000000
position (0,1): 1010110101
position (3,1): 1000110000
position (0,3): 1010000101
position (3,3): 1000000000
XOR: 0000000000 <- 0 means even number of all digits
对于直到右边缘或底边缘的矩形，仅对两个图案进行异或.对于直到右下角的矩形，可以简单地从矩阵中读取图案.
For rectangles up to the right or bottom edge, only two patterns are xor-ed. For rectangles up to the bottom-right corner, the pattern can simply be read from the matrix.
- - - - ---------- ---------- ---------- ----------
3 2 1 4 1010110101 ---------- ---------- ----------
1 3 2 5 ---------- ---------- ---------- ----------
- - - - 1010000101 ---------- ---------- ----------
position (0,1): 1010110101
position (0,3): 1010000101
XOR: 0000110000 <- non-zero means odd number of some digits
然后我们将检查整个矩形，然后将矩形缩小一排或一列，依此类推，从大到小.显然，可以跳过具有奇数行和列的矩形.
We'd then proceed by checking the whole rectangle, then the rectangles one row or column smaller, and so on, from large to small. Obviously, rectangles with an odd number of rows and columns can be skipped.
最糟糕的情况是N 2 (如果我们检查的最后一个矩形是唯一有效的解决方案).最好的情况是N(如果整个矩形是有效的解决方案)，则平均值取决于输入的细节.
The worst case complexity of this is N2 (if the last rectangle we check is the only valid solution). The best case is N (if the whole rectangle is a valid solution) and the average depends on the specifics of the input.
如果要尝试动态编程，请为每个2x1和1x2矩形构建一个带有位模式的表，然后对其中的两个进行xor运算以构建4x1、1x4和2x2矩形，依此类推...这需要xor-每个矩形设置2个图案，而非dp解决方案则需要对4个图案进行异或处理(对于直到右边缘或下边缘的矩形，则为2或0)，所以我不希望有重大改进.同样，如果最大的矩形之一是有效的解决方案，则可以在非dp解决方案中快速找到它，但只有在计算dp解决方案中的大多数矩形之后才能找到它.
If you want to try dynamic programming, build a table with the bit patterns for every 2x1 and 1x2 rectangle, then xor two of these to build up 4x1, 1x4 and 2x2 rectangles, and so on... This requires xor-ing 2 patterns per rectangle, whereas the non-dp solution requires xor-ing 4 patterns (or 2 or 0 for rectangles up to the right or bottom edge), so I don't expect major improvement. Also, if one of the largest rectangles is a valid solution, it would be found quickly in the non-dp solution, but only after calculating most of the rectangles in the dp solution.
我已经用一个简单的Javascript实现进行了一些测试，发现虽然理论上最坏的情况(检查具有偶数个元素的每个矩形)的确确实具有O(N 2 )，则平均大小写(当仅检查大于当前最佳解的矩形时)对于48x48及更大尺寸的矩形，其随机输入电平约为1314.因此，平均情况下的复杂度为O(N)，因为构建第二个矩阵成为主导因素. 2048x2048之类的大型案例可以在一秒钟内运行.
I've done some tests with a simple Javascript implementation, and found that while the theoretical worst case (checking every rectangle with an even number of elements) indeed has a complexity of O(N2), the average case (when checking only rectangles larger than the current best solution) with random input levels off at around 1314 for rectangles sized 48x48 and larger. So the average case complexity is O(N) because building the second matrix becomes the dominant factor; large cases like 2048x2048 can be run in under a second.
size N worst average max
2x2 4 5 4 5
3x3 9 20 14 20
4x4 16 64 40 64
5x5 25 144 81 144
6x6 36 297 155 297
7x7 49 528 250 528
8x8 64 896 375 896
9x9 81 1,400 496 1,355
10x10 100 2,125 614 1,981
11x11 121 3,060 698 2,876
12x12 144 4,320 770 3,883
13x13 169 5,880 815 5,098
14x14 196 7,889 866 6,603
15x15 225 10,304 897 7,729
16x16 256 13,312 937 8,123
...
20x20 400 32,000 1,057 9,019
24x24 576 65,664 1,144 9,640
32x32 1,024 204,800 1,248 10,521
40x40 1,600 496,000 1,293 10,369
48x48 2,304 1,022,976 1,306 11,006
64x64 4,096 3,211,264 1,314 11,334
80x80 6,400 7,808,000 1,314 10,962
96x96 9,216 16,146,432 1,312 10,970
128x128 16,384 50,855,936 1,318 10,875
最差"列显示的是面积均匀的矩形的数量；在最坏的情况下，必须检查所有这些矩形. 平均值"列显示了在从随机数变为大尺寸并跳过不大于目前找到的最大有效矩形的矩形时，在使用随机数据进行的测试中实际需要检查的矩形的平均数量. "max"列显示了测试中遇到的实际最坏情况；这似乎也稳定在48x48以上. (算法使用随机值对每种大小测试了1,000,000次.)
必须检查的矩形的平均数量当然与以下事实有关:具有随机数字的大矩形具有某个数字的偶数(但只有偶数)的概率约为1/2的事实.位数可以出现偶数次)，因此1/(C(10,0)+ C(10,2)+ C(10,4)+ C(10,6)+ C(10,8) + C(10,10))或全十位数的偶数的1/512.我平均得到1314而不是512的事实可能是因为我的算法不是严格地从大矩形变成小矩形，而是先尝试10x10，然后尝试9x10、10x9、8x10、10x8 ... 1x10、10x1，然后切换到8x9、9x8、6x9、9x6 ... 2x9、9x2，然后切换到8x8、7x8、8x7 ...以保持代码简单.如果完全优化，我希望大矩形框的平均值接近512.
The average number of rectangles that have to be checked is of course related to the fact that a large rectangle with random digits has a probability of around 1/2 of having an even number of a certain digit (but only an even number of digits can be present an even number of times) and thus 1/(C(10,0) + C(10,2) + C(10,4) + C(10,6) + C(10,8) + C(10,10)) or 1/512 of having an even number of all ten digits. The fact that I get an average of 1314 instead of 512 is probably because my algorithm doesn't strictly go from large to small rectangles, but tries 10x10 first, and then 9x10, 10x9, 8x10, 10x8 ... 1x10, 10x1, before switching to 8x9, 9x8, 6x9, 9x6 ... 2x9, 9x2, and then 8x8, 7x8, 8x7 ... to keep the code simple. If it were completely optimized, I'd expect the average to approach 512 for large rectangles.
当试图找出最坏的情况(没有有效矩形的矩阵)在大矩阵尺寸下是否可行时，我会根据以下顺序自动得出正方形:
When trying to find out whether the worst case, a matrix with no valid rectangles, was possible at large matrix sizes, I automatically arrived at squares based on this sequence:
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5...
，您可以通过重复到目前为止的序列并将最后一个数字加1来获得( OEIS A007814 ) .这将导致这些矩阵不包含矩形，每个矩形的偶数个数字为:
which you get by repeating the sequence so far, and adding 1 to the last number (OEIS A007814). This results in these matrices which contain no rectangles with even numbers of each digit:
0,1
1,2
0,1,0,2
1,2,1,3
0,1,0,2
2,3,2,4
0,1,0,2,0,1,0,3
1,2,1,3,1,2,1,4
0,1,0,2,0,1,0,3
2,3,2,4,2,3,2,5
0,1,0,2,0,1,0,3
1,2,1,3,1,2,1,4
0,1,0,2,0,1,0,3
3,4,3,5,3,4,3,6
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4
3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,7
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4
4,5,4,6,4,5,4,7,4,5,4,6,4,5,4,8
在他看来，如果您重复16x16矩阵以创建32x32矩阵，并在最右边的列和底部的行中加1，则右下角的单元格将具有值10；我们可以将其替换为1(但这是唯一起作用的值):
At his point, if you repeat the 16x16 matrix to create a 32x32 matrix and add 1 to the right-most column and bottom row, the bottom-right cell would have the value 10; we can replace this with a 1 (but that's the only value that works):
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,7
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,7,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,8
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,7
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
4,5,4,6,4,5,4,7,4,5,4,6,4,5,4,8,4,5,4,6,4,5,4,7,4,5,4,6,4,5,4,9
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,7
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,7,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,8
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,7
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5
5,6,5,7,5,6,5,8,5,6,5,7,5,6,5,9,5,6,5,7,5,6,5,8,5,6,5,7,5,6,5,1
然后，当从32x32变为64x64时，在最右边的列和底部的行中都有几个单元格，每个单元格的每个值都创建一个矩形，每个矩形的偶数个数.因此，产生最坏情况输入的最大正方形可能是以下63x63矩阵:
Then, when going from 32x32 to 64x64, there are several cells in the right-most column and bottom row for which every value creates a rectangle with an even number of each digit. So the maximum-sized square which creates the worst case input may be this 63x63 matrix:
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,7,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,7,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,8,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,7,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,7,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
4,5,4,6,4,5,4,7,4,5,4,6,4,5,4,8,4,5,4,6,4,5,4,7,4,5,4,6,4,5,4,9,4,5,4,6,4,5,4,7,4,5,4,6,4,5,4,8,4,5,4,6,4,5,4,7,4,5,4,6,4,5,4
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,7,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,7,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,8,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,7,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,7,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
5,6,5,7,5,6,5,8,5,6,5,7,5,6,5,9,5,6,5,7,5,6,5,8,5,6,5,7,5,6,5,1,5,6,5,7,5,6,5,8,5,6,5,7,5,6,5,9,5,6,5,7,5,6,5,8,5,6,5,7,5,6,5
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,7,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,7,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,8,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,7,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,7,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
4,5,4,6,4,5,4,7,4,5,4,6,4,5,4,8,4,5,4,6,4,5,4,7,4,5,4,6,4,5,4,9,4,5,4,6,4,5,4,7,4,5,4,6,4,5,4,8,4,5,4,6,4,5,4,7,4,5,4,6,4,5,4
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,7,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,7,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,8,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3,7,3,4,3,5,3,4,3,6,3,4,3,5,3,4,3
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,7,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2,6,2,3,2,4,2,3,2,5,2,3,2,4,2,3,2
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
如果这确实是最大的输入而没有矩形，每个矩形的偶数个数字是偶数(但我没有证明，并且我只考虑了平方矩阵)，那么这将使最大矩形数为3,015,680检查，对于大输入(大于1736x1736)，最坏情况下的复杂度也将变为O(N). (另请参见
If this is indeed the largest input without rectangles with even numbers of each digit (but I have no proof, and I've only considered square matrices), then that would put a maximum of 3,015,680 on the number of rectangles to be checked, and the worst case complexity would also become O(N) for large input (greater than 1736x1736). (See also this question on Mathematics.)
这篇关于搜索矩阵中数字为偶数的最大矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
