c - 查找稀疏矩阵中元素周围的最大区域

Question

我有一个稀疏矩阵数组，我需要在其中找到元素周围的最高空白区域。区域应为矩形或正方形。在该区域中不应存在其他元素。算法足以开发代码。有什么算法可以实现这一点吗？

Answer 1

由于您提到对解决方案的效率没有要求，因此这里有一个强力方法。

Let M denote the matrix
Let n be the number of rows
Let m be the number of columns
Let maxRowSize be 0, initially
Let maxColSize be 0, initially
Let maxRowStart be 0, initially
Let maxColStart be 0, initially
for top from 0 to n:
    for left from 0 to m:
        numNonEmptyElements = 0
        if M[top][left] is non-empty:
            numNonEmptyElements = 1
        for bottom from i to n:
            if M[bottom][left] is non-empty AND numNonEmptyElements == 1:
                break
            for right from 0 to m:
                if M[bottom][right] is non-empty:
                    numNonEmptyElements += 1
                if numNonEmptyElements > 1:
                    break
                if (right - left + 1) * (bottom - top + 1) > maxRowSize * maxColSize:
                    maxRowSize = bottom - top + 1
                    maxColSize = right - left + 1
                    maxRowStart = top
                    maxColStart = left
return any of the maxRowSize, maxColSize, maxRowStart, maxColStart you need

从循环中可以看出，伪代码的时间复杂度为O(N²M²)，N 和 M是矩阵的行和列的大小，效率很低。