| 比赛场次 | 432 |
|---|---|
| 比赛名称 | 论文练习 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2018-10-19 19:00:00 |
| 结束时间 | 2018-10-19 22:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 | 黄笑凡巨佬关于分享2003集训队论文《浅谈用极大化思想解决最大子矩形问题》后的练习 |
| 题目名称 | 巨大的牛棚 |
|---|---|
| 输入输出 | bigbrn.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试点数 | 15 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 梦那边的美好ET |
AAAAAAAAAAAAAAA | 0.237 s | 26.50 MiB | 100 |
|
aaaa1218 |
AAAAAAAAAATAAAA | 1.944 s | 7.05 MiB | 93 |
 云卷云书 |
AAAAAAAAAATTTTA | 5.615 s | 52.81 MiB | 73 |
USACO/bigbrn(译 by Felicia Crazy)
描述
农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树，想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定，他的农场划分成 N x N 的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚。牛棚的边必须和水平轴或者垂直轴平行。EXAMPLE
考虑下面的方格，它表示农夫约翰的农场，‘.'表示没有树的方格，‘#'表示有树的方格
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
最大的牛棚是 5 x 5 的，可以建造在方格右下角的两个位置其中一个。
PROGRAM NAME: bigbrn
INPUT FORMAT(file bigbrn.in)
| Line 1: | 两个整数： N （1 <= N <= 1000），农场的大小，和 T （1 <= T <= 10，000）有树的方格的数量 |
| Lines 2..T+1: | 两个整数（1 <= 整数 <= N), 有树格子的横纵坐标 |
OUTPUT FORMAT(file bigbrn.out)
输出文件只由一行组成，约翰的牛棚的最大边长。
SAMPLE INPUT (file bigbrn.in)
8 3
2 2
2 6
6 3
SAMPLE OUTPUT (file bigbrn.out)
5