[USACO5.3] 巨大的牛棚Big Barn

题目描述

FJ 有一个大小为 𝑛×𝑛n×n 的农场（1≤𝑛≤10001≤n≤1000），他想要在他的农场上建造一座正方形大牛棚。他的农场中有 𝑡t 棵果树（1≤𝑡≤100001≤t≤10000），但他为了不破坏果树，就想找一个空旷无树的地方修建牛棚。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚的边长。当然，牛棚的边必须和水平轴和垂直轴平行。

考虑下面的农场，. 表示没有树的方格，# 表示有树的方格。

0 1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .

Copy

最大的牛棚是边长为 55 的，可以建造在农场右下角的两个位置其中一个。

输入格式

第 11 行输入两个正整数 𝑛n 和 𝑡t。

第 2⋯𝑡+12⋯t+1 行输入两个正整数 𝑥,𝑦 (1≤𝑥,𝑦≤𝑛)x,y (1≤x,y≤n)。

输出格式

只由一行组成，约翰的牛棚的最大边长。

样例 #1

样例输入 #1

8 3
2 2
2 6
6 3

Copy

样例输出 #1

5

#include<bits/stdc++.h>
using namespace std;
long long n,m=1,f[2001][2001],x,a[5005],dp[2001][2001],mod=19650827,y,t;
int main(){
    cin>>n>>t;
    memset(dp,1,sizeof(dp));
    for(long long i=1;i<=t;i++){
        cin>>x>>y;
        dp[x][y]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(dp[i][j]!=0) f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;
            //m=max(m,f[i][j]);
        }        
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            //if(dp[i][j]==0) dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
            m=max(m,f[i][j]);
        }        
    }
    cout<<m;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
long long n,m=1,f[2001][2001],x,a[5005],dp[2001][2001],mod=19650827,y,t;
int main(){
	cin>>n>>t;
	memset(dp,1,sizeof(dp));
	for(long long i=1;i<=t;i++){
		cin>>x>>y;
		dp[x][y]=0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(dp[i][j]!=0) f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;
			//m=max(m,f[i][j]);
		}		
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			//if(dp[i][j]==0) dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
			m=max(m,f[i][j]);
		}		
	}
	cout<<m;
	return 0;
}