矩阵格查找的高效求解

G-Spider

今天有个同学问了个这个问题，他那里有个程序，跑20*30的矩阵用了14s (四核机)，更大一点的矩阵就基本求不出来，于是就有了这个需求。

问题形式是这样的：

有一个m*n 的矩阵(m,n 均比较大，比如均100左右，实际需求对于m 会更大， n<200左右)

元素只有4个，｛0，1，2，3｝ 其中0 表示无意义的值。

我们要在其中找到这样的矩阵，满足（矩阵的四个端点，上端与下端相等）如下：
a ..........b
.               .
.               .
.               .
a..........b

其中a,b ={1,2,3}，a与b可以相等或不等，但不能为0.
并且如果这个大矩阵中有更小的会被包含，不计。
找出所有这样的矩阵。

例如，下面的查找结果，有两个矩阵：


再看一例，也有两个矩阵满足：


大致就是这个意思，不知道表述清楚了没有，找到的矩阵可以用坐标表示即可。

litaoye

求全解么？还是求m*n的最大解？20 * 30跑14秒有些夸张，全解的话会比较慢，毕竟解的数量可能很多。
先统计出来每行1.2.3的坐标的集合，然后依次同后面的行求交集，应该就差不多了。

G-Spider

2# litaoye

求全解。那同学的初步想法是先统计出每列1.2.3的坐标的集合。

gxqcn

我觉得第一步应快速排除“0”的干扰：可将第k行中的“0”全部替换成(k+3)。

G-Spider

4# gxqcn
不会是想做减法运算吧。

zgg___

假设用最笨的办法，搜索m*n的矩阵中左上角为x*y的满足要求的矩形，计算量小于m*n次。
x和y的选取方式小于m*n种，因此总计算量会小于(m*n)^2次运算。
当m和n小于100时，运算量貌似并不是很大。

zeroieme

希哈表，O(n)的复杂度。

这里需要m+1个希哈表，所以O(m*n)的复杂度。