讨论一下careercup上的一道题，找周边全是1的最大子方阵 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

讨论一下careercup上的一道题，找周边全是1的最大子方阵

讨论一下careercup上的一道题，找周边全是1的最大子方阵# JobHunting - 待字闺中

A*r2010-09-17 07:09

1 楼

原题如下：
Imagine you have a square matrix, where each cell is filled with either
black or white. Design an algorithm to find the maximum subsquare such that
a ll four borders are filled with black pixels.
http://careercup.com/question?id=2445
大家都知道这是那道找全部为1的最大子方阵的变形（用DP可以达到O(N^2))，可是这道
题却不太能用那道题的方法，从optimal subproblem 无法得到下一个最优解。
CareerCup上给出了一种答案，也就是找出每一个可能的子方阵，然后测试它的四个边
是否满足条件。。这个首先不是DP, 另外他claim算法复杂度是O(N^2), 可是我怎么看
着像O(N^3),因为每找出一个子方阵，需要O(N^2), 但是对每一次方阵进行测试，也是
需要最坏O(N)的，请大家讨论讨论。。
给个例子
1 1 1 1 1

p*72010-09-17 07:09

2 楼

讨论过了。。。。
http://www.mitbbs.com/article_t/JobHunting/31677689.html

A*r2010-09-17 07:09

3 楼

谢谢，以前没看到。。
不过我怎么还是觉得这个的算法复杂度是O(N^3), DP的版本真复杂，我再仔细看看。。

【在 p********7 的大作中提到】

: 讨论过了。。。。
: http://www.mitbbs.com/article_t/JobHunting/31677689.html

A*r2010-09-17 07:09

4 楼

看晕了，尤其是遍历对角线那部分，能达到O(n^2)吗？
有没有前面参与讨论的明白人（han6, hock,paul, etc)出来给个总结版本。。

【在 p********7 的大作中提到】

: 讨论过了。。。。
: http://www.mitbbs.com/article_t/JobHunting/31677689.html

p*72010-09-17 07:09

5 楼

我觉得不是，但是也不是N^3。没仔细再想过。有空了再想想

【在 A*********r 的大作中提到】

: 看晕了，尤其是遍历对角线那部分，能达到O(n^2)吗？
: 有没有前面参与讨论的明白人（han6, hock,paul, etc)出来给个总结版本。。

h*62010-09-17 07:09

6 楼

对于每一条对角线，得到两组射线，在其中找出两条相互盖住对方起始点的射线，求最
长重叠区域。这个过程可以有O(nlogn)和O(n^2)的两种算法。
但是2n-1条对角线的数值并不是相互独立的，每一条对角线都只需要寻找比以前的结果更
长的重叠区域，因此可以大大缩短时间。最终我两种寻找重叠区域的算法运行时间都比求
前面几个矩阵的时间还短，因此我认为是O(n^2)的复杂度。

A*r2010-09-17 07:09

7 楼

如果真是这样的话，对于每一个点(i,j), 只用遍历它所对应的对角线，找出最大重叠
区域就可以了，不用再做其他的遍历了就可以确定C[i,j]的大小了。。
我copy你原来的code如下：
int DiagonalOverlap(int* B1, int* B2, int n, int lastresult)
{
int result = lastresult;
for(int i=0; i lastresult)
for(int j=0; j<=i; j++) if(B2[j] > lastresult)
{
if(i-j+1 <= min(B1[i], B2[j]))
result = max(result, i-j+1);
}
return result;
}
我现在想问，如果用DP的话，只查找对角线，C[i,j]的值怎么设置的呢？

果更
比求

【在 h**6 的大作中提到】

: 对于每一条对角线，得到两组射线，在其中找出两条相互盖住对方起始点的射线，求最
: 长重叠区域。这个过程可以有O(nlogn)和O(n^2)的两种算法。
: 但是2n-1条对角线的数值并不是相互独立的，每一条对角线都只需要寻找比以前的结果更
: 长的重叠区域，因此可以大大缩短时间。最终我两种寻找重叠区域的算法运行时间都比求
: 前面几个矩阵的时间还短，因此我认为是O(n^2)的复杂度。

h*62010-09-17 07:09

8 楼

我的算法不需要使用矩阵C。
矩阵B1、B2分别是每一点其左上、右下有多少连续的1，然后把这两个矩阵相同位置的
对角线拿出来，代入上面那个函数就可以了。

A*r2010-09-17 07:09

9 楼

那样的话，算法复杂度就是O(N^3)了.
一共有O(N)条对角线，你的code对每条对角线找需要O(N^2),所以会是O(N^3).
我知道你提及到每条对角线应该不是独立的，那么就需要一个递推从一条对角线的最大
重叠区域来算出下一条的重叠区域，而不是单纯的把每条对角线代入那个函数。。
有了这个递推公式，才有可能把算法复杂度降到O(N^2)..我目前还没想出来这个递推公
式，觉得很难，毕竟一个O(N^2)的计算，要在O(1)里就完成，好悬。。

【在 h**6 的大作中提到】

: 我的算法不需要使用矩阵C。
: 矩阵B1、B2分别是每一点其左上、右下有多少连续的1，然后把这两个矩阵相同位置的
: 对角线拿出来，代入上面那个函数就可以了。

h*k2010-09-17 07:09

10 楼

他那个算法有问题，原贴我给出的几个case他的算法没有办法正确计算。
我比较怀疑这个问题有O(n^2)的算法。

【在 A*********r 的大作中提到】

: 如果真是这样的话，对于每一个点(i,j), 只用遍历它所对应的对角线，找出最大重叠
: 区域就可以了，不用再做其他的遍历了就可以确定C[i,j]的大小了。。
: 我copy你原来的code如下：
: int DiagonalOverlap(int* B1, int* B2, int n, int lastresult)
: {
: int result = lastresult;
: for(int i=0; i lastresult)
: for(int j=0; j<=i; j++) if(B2[j] > lastresult)
: {
: if(i-j+1 <= min(B1[i], B2[j]))

A*r2010-09-17 07:09

11 楼

看来我还是不要纠结这道题了，还是抓紧时间准备其他的，还有好多没看呢。。

【在 h**k 的大作中提到】

: 他那个算法有问题，原贴我给出的几个case他的算法没有办法正确计算。
: 我比较怀疑这个问题有O(n^2)的算法。