Problem Link：http://acm.hdu.edu.cn/showproblem.php?pid=4846

 

Big Barn

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 296    Accepted Submission(s): 145

Problem Description

　　农夫John想在他的正方形农场上建一个正方形谷仓。他不想在他的农场砍伐树木，所以他要为他的谷仓找一个位置，使他在没有树的地方建谷仓。农场被划分为N×N（N≤1000）块。输入给出这些块的一个列表，在有些块内生长着树。请您找出最大的一个不包含任何树的一块正方形场地。谷仓的边必须与水平轴或垂直轴平行。 　　例如，下面给出的是农夫John的土地，其中`.' 表示在这个块中没有树木，而`#'表示这个块中有树木： 1 2 3 4 5 6 7 8 1 . . . . . . . . 2 . # . . . # . . 3 . . . . . . . . 4 . . . . . . . . 5 . . . . . . . . 6 . . # . . . . . 7 . . . . . . . . 8 . . . . . . . . 　　最大的谷仓是5×5，可修建在网格右下方的两个位置之一。

Input

　　有多组输入数据.(少于20组) 对于每一组数据,首先给出两个整数：N（1≤N≤1000），块的数量；和T（1≤T≤10000），有树的块的数量。第2行到第T+1行，每行两个整数，在区间[1, N]中取值，表示有树的一个块的行和列。

Output

　　对于每一组数据,单独输出一行表示John的正方形谷仓的最大边长。

Sample Input

8 3 2 2 2 6 6 3

Sample Output

5

 

AC code1（DP）：

#include<bits/stdc++.h> using namespace std; const int maxn=1010; int dp[maxn][maxn];//dp[i][j]代表以(i,j)为右下角顶点的正方形的最大边长 int m[maxn][maxn]; int main() { //freopen("D:\\in.txt","r",stdin); int N,T,r,c,ans; while(scanf("%d%d",&N,&T)!=EOF) { for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { m[i][j]=1; } } while(T--) { scanf("%d%d",&r,&c); m[r][c]=0; } memset(dp,0,sizeof(dp)); ans=0; for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { if(m[i][j]==1) { //状态转移方程 dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1; } ans=max(ans,dp[i][j]); } } printf("%d\n",ans); } return 0; }

 

AC code2（单调栈）：

#include<bits/stdc++.h> using namespace std; const int maxn=1010; int l[maxn],r[maxn],h[maxn]; int m[maxn][maxn]; int main() { //freopen("D:\\in.txt","r",stdin); int n,T,row,col,ans; while(scanf("%d%d",&n,&T)!=EOF) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { m[i][j]=1; } } while(T--) { scanf("%d%d",&row,&col); m[row][col]=0; } memset(h,0,sizeof(h)); ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(m[i][j]==1) { h[j]++; } else { h[j]=0; } } int k; h[0]=-1; h[n+1]=-1; for(int j=1;j<=n;j++) { k=j; while(h[j]<=h[k-1]) { k=l[k-1]; } l[j]=k; } for(int j=n;j>=1;j--) { k=j; while(h[j]<=h[k+1]) { k=r[k+1]; } r[j]=k; } for(int j=1;j<=n;j++) { //ans=max(ans,h[j]*(r[j]-l[j]+1)); ans=max(ans,min(h[j],r[j]-l[j]+1)); } } printf("%d\n",ans); } return 0; }