hdu 4846 Big Barn（一番大全の1正方形を求めます）

Problem Link：http://acm.hdu.edu.cn/showproblem.php?pid=4846
 
Big Barn
Time Limit：3000/1000 MS（Java/Others）    メモリLimit：65535/32768 K（Java/Others）Total Submission（s）：296    Acceepted Submission(s)：145
Problem Description
農夫のジョンさんは彼の正方形の農場に四角形の穀倉を作りたいです。彼は彼の農場で木を伐採したくないので、彼は彼の穀倉のために位置を探して、彼に木のないところに穀倉を建てさせます。農場はNに分けられている×N（N≦1000）ブロックです。これらのブロックのリストを入力して、いくつかのブロック内に木が成長しています。一番大きいのは木を含まない正方形の場所を探してください。谷倉の辺は水平軸または垂直軸と平行でなければならない。例えば、以下に示すのは农夫のJohnの土地です。このブロックに木がないことを表しています。このブロックに木があることを表しています。1.3.4.5.6.8.1..............（2）×5,グリッドの右下の2つの位置の一つを構築できます。
Input
複数の入力データのセットがあります。（20未満のグループ）各データのセットに対して、まず2つの整数を与えます。N（1≦N≦1000）、ブロックの数。和T(1≦T≦10000)は、木のあるブロックの数です。2行目からT＋1行目までの2つの整数は、区間［1，N］で値をとり、ツリーのあるブロックの行と列を表します。
Output
各グループのデータに対して、単独で出力する行はジョンの正方形の穀倉の最大辺の長さを表します。
Sample Input
8 3 2 2 2 2 6 3
Sample Output
5
 
ACコード1（DP）：

#include
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
",ans);
	}
	return 0;
}

 
ACコード2（単調スタック）：

#include
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
",ans);
	}
	return 0;
}