[USACO5.3] 巨大的牛棚Big Barn
题目背景
(USACO 5.3.4)
题目描述
FJ 有一个大小为 $n\times n$ 的农场($1\le n\le 1000$),他想要在他的农场上建造一座正方形大牛棚。他的农场中有 $t$ 棵果树($1\le t\le10000$),但他为了不破坏果树,就想找一个空旷无树的地方修建牛棚。你的任务是计算并输出,在他的农场中,不需要砍树却能够修建的最大正方形牛棚的边长。当然,牛棚的边必须和水平轴和垂直轴平行。
考虑下面的农场,`.` 表示没有树的方格,`#` 表示有树的方格。
```plain
0 1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
```
最大的牛棚是边长为 $5$ 的,可以建造在农场右下角的两个位置其中一个。
输入输出格式
输入格式
第 $1$ 行输入两个正整数 $n$ 和 $t$。
第 $2\cdots t+1$ 行输入两个正整数 $x,y\ (1\le x,y\le n)$。
输出格式
只由一行组成,约翰的牛棚的最大边长。
输入输出样例
输入样例 #1
8 3
2 2
2 6
6 3
输出样例 #1
5
说明
题目翻译来自NOCOW。
USACO Training Section 5.3