algorithm - am X n 矩阵中的最大平方数

Question

问题是 ：

给定一个包含 1.s 和 0 的 M x N 阶矩阵，您必须找到可以形成的最大平方数。正方形是通过将包含 1 的相邻单元格组合在一起形成的。最大正方形是不完全包含在另一个正方形中的正方形。部分重叠的最大正方形将单独计算。单位正方形（边长 = 1）也应计算在内。请注意，正方形是填充的，即它们不能包含 0.s。什么是最好的算法？

例子 ：

对于以下 4x5 矩阵，输入将是：

样本输入和输出：

11001
11110
11011
11001

输出：

9

Answer 1

设S(i,j)为右下角为 的最大正方形的大小(i,j)。（我的索引从上到下，从左到右，从 1 开始。）整体S是一个M x N整数矩阵。计算S是动态规划中非常经典的问题，已知它具有 O(MN) 时间复杂度。（如果你不记得了，这里是如何完成的。假设A是输入矩阵。你设置S(i,j) = 0if A(i,j) = 0，并设置S(i,j) = min(S(i-1,j), S(i,j-1), S(i-1,j-1))+1if A(i,j) = 1。你可以设置S(0,j) = S(i,0) = 0如果你喜欢。）

然后通过检查矩阵来提取最大平方S。(i,j)当且仅当S(i,j)非零且大于或等于S(i+1,j)，S(i,j+1)且时，右下角为 的正方形是最大的S(i+1,j+1)。（设置S(M+1,j) = 0，S(i,N+1) = 0如果你喜欢。）这一步也需要 O(MN) 时间。

Answer 2

可能的 4x4 正方形在 (0,0) 和 (1,0) 处具有左上角。

可能的 3x3 正方形在 (0,0)、(1,0)、(2,0)、(0,1)、(1,1)、(2,1) 处具有左上角。

可能的 2x2 正方形在 (0,0), (1,0), (2,0), (3,0), (0,1), (1,1), (2,1) 处有左上角， (3,1), (0,2), (1,2), (2,2), (3,2)。

可能的 1x1 正方形在所有坐标处都有左上角。

所以一个算法可以如下：

从测试 4x4 开始，如果全为 1，则标记为属于 4x4，并增加计数。

然后测试 3x3，如果全 1 且未标记为属于 4x4，则标记为属于 3x3，并增加计数。

然后测试 2x2，如果全 1 且未标记为属于 4x4 或 3x3，则标记为属于 2x2，并增加计数。

然后测试 1x1，如果 1 并且根本没有标记，则增加计数。

返回计数。

您如何标记单元格将是特定于语言的。例如，对于 C，我会使用位域。

编辑：为了好玩，我使用 Bitset 在 Java 中实现了这个。

import java.util.BitSet; 

public class Program
    {
    // Right-shift bits by 'n' places
    private static BitSet RightShift(BitSet x, int n)
        {
        return x.get(n, Math.max(n, x.length()));
        }

    // Test square of dimension 'size' with top-left at position (h,w) for maximal-ness
    public static boolean IsMaximalSquare(BitSet [][] matrix, int h, int w, int size)
    {
        boolean isMaximal = true;
        for (int a = 0; a < size; a++)
        {
            for (int b = 0; b < size; b++)
            {
                BitSet x = matrix[h + a][w + b];
                if (!x.get(0))
                    return false;
                x = RightShift(x, size + 1);
                if (!x.isEmpty())
                    isMaximal = false;
            }
        }

        if (!isMaximal)
            return false;

        for (int a = 0; a < size; a++)
        {
            for (int b = 0; b < size; b++)
                matrix[h + a][w + b].set(size);
        }

        return true;
    }

    // Populate a 2d array of bitsets from string array
    public static BitSet [][] BuildMatrix(String rows[])
    {
        BitSet [][] matrix = new BitSet[4][5];

        for (int i = 0; i < 4; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                matrix[i][j] = new BitSet(5);
                matrix[i][j].set(0, '1' == rows[i].charAt(j));
            }
        }
        return matrix;
    }

    // Return number of maximal squares from string representation of array
    public static int Solve(String rows[])
    {
        BitSet [][] matrix = BuildMatrix(rows);

        int count = 0;

        for (int size = 4; size > 0; size--) // test squares of size 4x4, 3x3, 2x2 and 1x1
        {
            for (int h = 0; h < 5 - size; h++) // iterate the rows
            {
                for (int w = 0; w < 6 - size; w++) // iterate the columns
                {
                    if (IsMaximalSquare(matrix, h, w, size))
                        count++;
                }
            }
        }

        return count;
    }

    public static void main(String[] args)
        {
        String rows1[] = {"11001","11110","11011","11001"}; // original question
        String rows2[] = {"11111","11111","11111","11111"}; // additional test case 1
        String rows3[] = {"00000","00000","00000","00000"}; // additional test case 2
        String rows4[] = {"11100","11111","11111","00111"}; // additional test case 3
        String rows5[] = {"11101","11111","11111","10111"}; // additional test case 4

        System.out.println(Solve(rows1));
        System.out.println(Solve(rows2));
        System.out.println(Solve(rows3));
        System.out.println(Solve(rows4));
        System.out.println(Solve(rows5));
        }
    }