遍历二维数组的所有子数组
Traversing all the subarrays of a 2-D array
我有一个大小为 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] 中。
我在实现这个时遇到了问题，因为我不知道如何遍历给定索引的所有子数组。我已经尝试了很长时间，但仍然没有实现。有人可以帮忙吗？
It helps to simplify the problem to depend only on individual values (rather than pairs of neighboring values). So XOR the grid with each perfect checkerboard:
01111111 10000000
10111111 01000000
11111111 00000000
11111111 00000000
11111111 00000000
11111111 00000000
11111111 00000000
11111111 00000000
where the goal is now to find the largest square in either grid that has no more than K_i 0s (obviously favoring the left one here).
Start with K_i=0. To find the largest square of 1s, compute for each cell the number of 1s in a row and a column starting at it (0 for a cell that contains a 0); the largest square with that cell as its upper-left corner (assuming it's a 1) is then one more than the minimum of the row length of its right neighbor, the column length of its lower neighbor, and the square-size of its lower-right neighbor. (All these are 0 for the non-existent cells outside the grid.) Visit the cells in diagonal-major order to have these values available when you need them; note the largest square size produced.
To generalize to K_i>0, store for each cell those three values (row length, column length, and square size) for each number of flips up to K_i. A cell with a 1 adds 1 to each row/column length as before, while a cell with a 0 shifts those lengths to the next flip count, discarding those whose flip count is now too large and adding a new value of 0 for 0 flips. For each combination of row-length-east, column-length-south, and square-size-southeast, each with a flip count, a cell gets a candidate square size that is their minimum with the sum of their flip counts, plus one if the cell is a 0 itself. For each flip count (that isn't too large), keep the largest square size, noting if it is the largest so far encountered (for that flip count).
Note that the brute-force solution may be nearly as fast when the squares are much smaller than the array, since it need visit each one only a small number of times.
我有一个大小为 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] 中。 我在实现这个时遇到了问题，因为我不知道如何遍历给定索引的所有子数组。我已经尝试了很长时间，但仍然没有实现。有人可以帮忙吗？
It helps to simplify the problem to depend only on individual values (rather than pairs of neighboring values). So XOR the grid with each perfect checkerboard:
01111111 10000000
10111111 01000000
11111111 00000000
11111111 00000000
11111111 00000000
11111111 00000000
11111111 00000000
11111111 00000000
where the goal is now to find the largest square in either grid that has no more than K_i 0s (obviously favoring the left one here).
Start with K_i=0. To find the largest square of 1s, compute for each cell the number of 1s in a row and a column starting at it (0 for a cell that contains a 0); the largest square with that cell as its upper-left corner (assuming it's a 1) is then one more than the minimum of the row length of its right neighbor, the column length of its lower neighbor, and the square-size of its lower-right neighbor. (All these are 0 for the non-existent cells outside the grid.) Visit the cells in diagonal-major order to have these values available when you need them; note the largest square size produced.
To generalize to K_i>0, store for each cell those three values (row length, column length, and square size) for each number of flips up to K_i. A cell with a 1 adds 1 to each row/column length as before, while a cell with a 0 shifts those lengths to the next flip count, discarding those whose flip count is now too large and adding a new value of 0 for 0 flips. For each combination of row-length-east, column-length-south, and square-size-southeast, each with a flip count, a cell gets a candidate square size that is their minimum with the sum of their flip counts, plus one if the cell is a 0 itself. For each flip count (that isn't too large), keep the largest square size, noting if it is the largest so far encountered (for that flip count).
Note that the brute-force solution may be nearly as fast when the squares are much smaller than the array, since it need visit each one only a small number of times.