找到给定矩阵中的最大模式

Question

我是算法问题世界的新手，这个问题一直让我很头疼。我一直试图解决这个问题了几天，在这一点上，我感到有点失落。我有一个解决方案，但是对于巨大的输入来说太慢了，所以我目前正在寻找更有效的方法。

目标是在给定的由点('.')，圆('o')和X字母('X')组成的矩阵中找到形状为H的图案的最大SIZE(输出是数字)。这个矩阵有m行n列。2≤m, n≤2000.

图案必须由点('.')组成，最多只能包含一个圆('o')。图案不能包含任何"X"字母。图案由左柱、右柱和中柱组成，中柱不能碰到左柱和右柱的上、下。

例如:

X...
.o..
X...
..o.

在上面的矩阵中，H的最大大小为9。

允许使用以下模式:

. .     .       .                                              
. o     .       .
. .     .........
. .     .       .    . .
...     .       .    ...
. .     .       .    . .

，但这些变体是不允许的:

.    o 
.    .
.    .
.    .
......            
.....o 
.    .
.    .
.    .
.    .    

我一直在思考这个问题的方式:

我的简单解决方案是这样的:

for (int leftCol = 0; leftCol < n - 2; leftCol ++ ){
for (int rightCol = n-1; rightCol > leftCol + 1; rightCol--){
//searchForBiggestHLeftO() with 'o' in the "left pillar" of H between rightCol and leftCol
//searchForBiggestHRightO() with 'o' in the "right pillar" of H between rightCol and leftCol
//searchForBiggestHMiddleO() with 'o' in the "middle pillar" of H between rightCol and leftCol
//searchForBiggestH() without any 'o' between rightCol and leftCol
}  
}

上面的解决方案(即使它有效)对于更大的矩阵(数百x数百甚至数千x数千)变得无用。从那以后，我一直在尝试寻找其他更有效的方法来计算h的大小。

我在网上发现的最类似的问题是如何在二进制矩阵中找到由'1'组成的形状'+'的最大模式的解决方案。

https://www.geeksforgeeks.org/find-size-of-the-largest-formed-by-all-ones-in-a-binary-matrix/

但不幸的是，我还没有能够以任何有效的方式应用解决算法。图案可能包含一个圆圈"o"，这一事实成为我的绊脚石。

我相信有一些方便的方法来看待这个问题，我没有看到。谢谢你的宝贵时间。

Answer 1

在O(mnn)时间内，我们可以计算每个矩阵条目

• 它的上方(下方、左侧、右侧)有多少个连续的点
• 它的上方(下方、左侧、右侧)有多少连续条目既不是X也不是第二个圆

通过上下扫描每列，左右扫描每行。这导致了一个O(m n²)时间的算法，通过迭代行，迭代行中对条目(即，猜测H的3度顶点)，在上面的计算上做恒定的工作。

实际上我认为我们可以做得更好。这里是粗略的细节，但是猜测行(即，迭代行)，根据它们在包含和不包含圆圈时可以达到的高度对列进行排序，并使用 操作以高度递减的顺序将它们插入在线数据结构中。

• 插入(我、深度)
• Query(i '， depth '):返回先前插入的(i, depth)的最大值|i−i ' | + min(depth, depth ')，

使用适当增强的段树实现。