Google: 最大无障碍点子矩阵

a) There is a square of nxn size which is comprised of n-square 1x1 squares.
Some of these 1x1 squares are colored. Find the biggest sub square which is not colored.
b) Also asked to extend it to find the biggest area rectangle.

这题有难度

最大0-1子矩阵啊，可以做到O(n^2).
记录下每个点当前向上最大高度h[i,j]，以及保持该高度下，向左left[i][j]，向右right[i][j]，可以延伸多远,
答案就是max_{i,j} h[i][j]*(right[i][j] - left[i[j]+1).


怕麻烦的话用最大子矩阵的算法，O(n^3)

最大0-1子矩阵啊，可以做到O(n^2).
记录下每个点当前向上最大高度h，以及保持该高度下，向左left[j]，向右right[j]，可以延伸多远,
答案就是max_{i,j} h[j]*(right[j] - left+1).


怕麻烦的话用最大子矩阵的算法，O(n^3)
Narashy 发表于 2011-7-5 02:13

有O(N)的解法，动态规划。
方程就是: F(i,j) = 0 : 1+min(F(i-1,j), F(i,j-1), F(i-1,j-1))
F(i,j)代表以M[i][j]为top right顶点的最大满足要求的square.
方程得到的方式可以这么想，以F(i,j)为出发点，每次向横坐标减一，纵坐标减一这样扩展。
最大矩阵的话也是类似的思路。

代码：

1. 
   
2. void GetMaxSquare(int M[N][N])
   
3. {
   
4.         int REC[N][N];
   
5.         int nMaxLen = -1;
   
6.         int x = 0;
   
7.         int y = 0;
   
8. 
   
9.         for (int i = 0; i < N; i++)
   
10.         {
    
11.                 if ((REC[i][0] = M[i][0]) > nMaxLen)
    
12.                 {
    
13.                         x = i;
    
14.                         y = 0;
    
15.                         nMaxLen = REC[i][0];
    
16.                 }
    
17. 
    
18.                 if ((REC[0][i] = M[0][i]) > nMaxLen)
    
19.                 {
    
20.                         x = 0;
    
21.                         y = i;
    
22.                         nMaxLen = REC[0][i];
    
23.                 }
    
24.         }
    
25. 
    
26.         for (int i = 1; i < N; i++)
    
27.                 for (int j = 1; j < N; j++)
    
28.                 {
    
29.                         if (0 == M[i][j])
    
30.                         {
    
31.                                 REC[i][j] = 0;
    
32.                                 continue;
    
33.                         }
    
34. 
    
35.                         int nMin = REC[i-1][j] < REC[i][j-1] ? REC[i-1][j] : REC[i][j-1];
    
36.                         nMin = nMin < REC[i-1][j-1] ? nMin : REC[i-1][j-1];
    
37.                         REC[i][j] = nMin + 1;
    
38. 
    
39.                         if (nMaxLen < REC[i][j])
    
40.                         {
    
41.                                 x = i;
    
42.                                 y = j;
    
43.                                 nMaxLen = REC[i][j];
    
44.                         }
    
45.                 }
    
46. 
    
47.         cout<<x-nMaxLen+1<<" "<<y-nMaxLen+1<<" "<<x<<" "<<y<<endl;
    
48. }
    

复制代码

回复 4# wwwyhx


   你这个是O(n^2)的算法啊（你说的N是矩阵地边长而不是面积吧）。是解square的情形的。rectangle貌似解不了。

当然，看这个n代表的是什么了，如果是矩阵长度，那就是O(n^2),再快也要先遍历一遍吧，哈哈。

换种想法就可以解rectangle 了，用两个matrix[n,n]来做DP,一个记录长，一个记录宽，主要思想还是类似的，就是从i,j纵向扩展的限制，i,j开始横向扩展的限制规律推导方程，太麻烦懒得做了

回复  wwwyhx


   你这个是O(n^2)的算法啊（你说的N是矩阵地边长而不是面积吧）。是解square的情形的。rectangle貌似解不了。

当然，看这个n代表的是什么了，如果是矩阵长度，那就是O(n^2),再快也要先遍历一遍吧，哈哈。

换种想法就可以解rectangle 了，用两个matrix[n,n]来做DP,一个记录长，一个记录宽，主要思想还是类似的，就是从i,j纵向扩展的限制，i,j开始横向扩展的限制规律推导方程，太麻烦懒得做了
Narashy 发表于 2011-7-6 00:21

不好意思，引用点成编辑了。觉得这题好难，我是看别人的解法的

最大0-1子矩阵啊，可以做到O(n^2).
记录下每个点当前向上最大高度h，以及保持该高度下，向左left[j]，向右right[j]，可以延伸多远,
答案就是max_{i,j} h[j]*(right[j] - left+1).


怕麻烦的话用最大子矩阵的算法，O(n^3)
Narashy 发表于 2011-7-5 02:13

你这个思路如何保证O(n^2)??
计算“延伸多远”可以做到O(1)吗

回复 7# wwwyhx

我觉得你那个用亮哥矩阵分别记录长宽地方法不太可行。。

left[i][j] = left[i][j-1]      if h[i][j-1] >= h[i][j]    else j
  right[i][j] = right[i][j+1]  if h[i][j+1] >= h[i][j]  else j

回复  wwwyhx

我觉得你那个用亮哥矩阵分别记录长宽地方法不太可行。。

left[j] = left[j-1]      if h[j-1] >= h[j]    else j
  right[j] = right[j+1]  if h[j+1] >= h[j]  else j
Narashy 发表于 2011-7-6 00:48

和方形是一个原理吧，就是f(i,j)记录坐标(i,j)上的最优解，
i,j向两边扩展会受到f(i-1,j),f(i-1,j-1),f(i,j-1)的限制得出状态转移方程。
区别是方形必须两边同时扩展，矩阵不需要遵守

回复 9# wwwyhx


  恩！这题可以用这个一模一样的题测一下：
http://poj.org/problem?id=3494
附上我的code：

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <algorithm>
   
4. #include <cstring>
   
5. 
   
6. using namespace std;
   
7. 
   
8. const int N = 2010;
   
9. 
   
10. int m, n;
    
11. int h[N][N], lt[N], rt[N];
    
12. 
    
13. int main()
    
14. {
    
15.         int i, j, k, ans;
    
16. 
    
17.         while(scanf("%d%d",&m,&n)==2)
    
18.         {
    
19.                 memset(h, 0, sizeof(h));
    
20.                 ans = 0;
    
21.                
    
22.                 for(i=1;i<=m;i++){
    
23.                         for(j=1;j<=n;j++){
    
24.                                 scanf("%d",&k);
    
25.                                 h[i][j] = k? 1+h[i-1][j]: 0;
    
26.                                 lt[j] = rt[j] = j;
    
27.                         }
    
28.                         h[i][0] = h[i][n+1] = -1;
    
29.                         for(j=1;j<=n;j++)
    
30.                         {
    
31.                                 while(h[i][j]<=h[i][lt[j]-1]) lt[j]=lt[lt[j]-1];
    
32.                                 while(h[i][n-j+1]<=h[i][rt[n-j+1]+1]) rt[n-j+1]=rt[rt[n-j+1]+1];
    
33.                         }
    
34. 
    
35.                         for(j=1;j<=n;j++)
    
36.                                 ans = max(ans, h[i][j]*(rt[j]- lt[j]+1));
    
37.                 }
    
38.                 printf("%d\n",ans);
    
39.         }
    
40.         return 0;
    
41. }
    
42.                                                   
    
43. 
    
44.                
    

复制代码