c++ - 遍历二维数组的所有子数组

Question

我有一个大小为 P*Q 的二维数组，我必须根据该数组回答 K 个问题。给定的二维数组由数字 0 和 1 组成。对于每个问题，我们必须计算其中没有两个相同元素相邻的任何方形子数组的最大大小。 例如，如果 P=Q=8 并且我们给定的数组是

00101010
00010101
10101010
01010101
10101010
01010101
10101010
01010101

然后问题 Ki 允许我们进行 Ki 次翻转(0 到 1 或 1 到 0。)

Here K=4(number of questions)
1 2 0 10001
Output: 7 8 6 8

我理解到对于K1=1，我们可以将数组index(1,1)的值改为1，得到一个7*7大小的有效矩阵，输出为7。如果我们有Ki>=2我们的答案是 8。 我的想法是，我们必须维护一个数组 ans[k]，它存储有效的方形子矩阵的最大大小。为此，我们可以启动原始数组的每个索引并遍历其子数组，如果我们从该索引开始计算 flip=i 的最大大小值。我们必须对从每个索引开始的子数组执行此操作，然后将它们的最大值存储在 flip[i] 中。 我在实现这个时遇到了问题，因为我不知道如何遍历给定索引的所有子数组。我已经尝试了很长时间，但仍然没有实现。有人可以帮忙吗？

Answer 1

它有助于简化问题以仅依赖于单个值(而不是成对的相邻值)。因此，XOR 网格与每个完美棋盘:

01111111  10000000
10111111  01000000
11111111  00000000
11111111  00000000
11111111  00000000
11111111  00000000
11111111  00000000
11111111  00000000

现在的目标是在任一个网格中找到不超过K_i 0 的最大方 block (这里显然偏向左边的方 block )。

从 K_i=0 开始。要找到 1 的最大正方形，请为每个单元格计算从它开始的行和列中 1 的数量(0 表示包含 0 的单元格)；以该单元格为左上角(假设它是 1)的最大正方形 比其右侧相邻行长度的最小值 多一个，列它的下邻居的长度，以及它的右下邻居的平方大小。 (对于网格外不存在的单元格，所有这些都是 0。)访问 diagonal-major 中的单元格，以便在需要时可以使用这些值；注意生成的最大正方形尺寸。

要推广到 K_i>0，请为每个单元格存储这三个值(行长、列长和正方形大小)每个翻转次数，直到 < em>K_i。带有 1 的单元格像以前一样将每行/列长度加 1，而带有 0 的单元格移动这些长度到下一个翻转计数，丢弃那些翻转计数现在太大了，为 0 次翻转添加了一个 新值 0。对于 row-length-east、column-length-south 和 square-size-southeast 的每个组合，每个组合都有一个翻转计数，一个单元格获得一个候选正方形大小，这是它们的最小值，<他们翻转计数的 em>总和，如果单元格本身是 0，则加一。对于每个翻转计数(不太大)，保持最大的正方形大小，注意它是否是迄今为止遇到的最大(对于该翻转计数)。

请注意，当方 block 比数组小得多时，暴力解决方案的速度可能几乎一样快，因为它只需要访问每个方 block 很少的次数。