USACO巨大牛棚（DP）

农夫约翰想在他的正方形农场中建一个巨大的正方形牛棚。

他不愿意在农场中砍伐树木，因此，他想要找一片平坦的土地，可以让他不需伐木就可直接在那里进行牛棚的搭建。

为了达到这一目的，我们将他的农场划分为 N×N 个方格区域。

给定包含树木的方格区域的数量，以及这些区域的具体位置。

请你计算，他在不砍伐树木的情况下，最大可以建造多大的牛棚。

搭建牛棚时，牛棚的四个边必须是水平或垂直的。

下面是一个农场的示例，其中，包含树木的方格区域用 “#” 表示，不包含树木的方格区域用 “.” 表示，具体表示为：

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

可建造的最大牛棚的尺寸为 5×5，具体位置在右下角。

输入格式
第一行包含两个整数 N 和 T，分别表示农场尺寸以及包含树木区域的数量。接下来 T 行，每行包含两个整数 X,Y，表示第 X 行第 Y 列的方格区域内包含树木。输出格式
输出一个整数，表示可建造的最大牛棚的边长。数据范围
1≤N≤1000,
1≤T≤10000,
1≤X,Y≤N
输入样例：
8 3
2 2
2 6
6 3
输出样例：
5

#include 
#include 
#include using namespace std;const int N = 1010;int n, m;
int g[N][N], f[N][N];//f[i][j]表示以(i,j)点为右下角的最大正方形边长int main()
{cin >> n >> m;while (m -- ){int x, y;cin >> x >> y;g[x][y] = 1;}int res=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if (!g[i][j]){f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;res = max(res, f[i][j]);}}}cout << res << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！