arrays - 在矩阵中找到可以从一个角移动到另一个角的最大正方形

Question

例如，你有一个 0 和 1 的矩阵:

1 1 1 0
1 1 1 0
1 1 1 0
1 1 1 1
0 1 1 1
1 0 1 1

在位置(0,0)放置一个正方形，求从左上角移动到右下角的所有1的最大正方形的大小。正方形只能向下和向右移动，并且只能越过为 1 的元素。

本例中最大正方形的大小为2，正方形中元素的索引为(0,0)、(0,1)、(1,0)、(1,1)。

我不确定如何解决这个问题。我想首先，你需要找到左上角的所有方 block 和右下角的所有方 block 。如果移动是可能的，那么这两个位置必须有相同大小的正方形。然后只尝试将左角的方 block 移动到与右角的方 block 大小相等的方 block 。但我不确定如何找到方 block 并检查它们是否可以移动。

Answer 1

您可以使用动态规划。

1. 假设 max_size(i, j) 是可以留在 (i, j) 单元格中的最大正方形的大小(可能为 0 )(停留意味着它的左上角位于这个单元格中)。我们可以用一种简单的方式计算这个值(通过迭代地增加正方形的大小并检查它不接触任何 0)。如果简单的解决方案不可行，我们可以对答案和前缀总和使用二分搜索，以获得每个单元格的 O(log n) 时间。

2. 假设 f(i, j) 是可以到达 (i, j) 单元格的最大正方形。基本情况:f(0, 0) = max_size(0, 0)(我们总能到达左上角)。对于其他单元格，可以通过以下方式计算(我在这里省略了极端情况):

   for i <- 0 ... n - 1:
       for j <- 0 ... m - 1:
           f(i, j) = min(max_size(i, j), max(f(i - 1, j), f(i, j - 1)))
   

3. 答案是最大的 f(i, j) 使得 i + f(i, j) - 1 = n - 1 和 j + f(i, j) - 1 = m - 1。

时间复杂度是O(n * m * log(min(n, m)))。