农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树,想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定,他的农场划分成 n * n
的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出,在他的农场中,不需要砍树却能够修建的最大正方形牛棚。牛棚的边必须和水平轴或者垂直轴平行。
考虑下面的方格,它表示农夫约翰的农场,‘.'表示没有树的方格,‘#'表示有树的方格
........
.#...#..
........
........
........
..#.....
........
........
那么最大的牛棚是5*5
的。
第一行输入一个正整数 代表农场的大小,一个正整数, 接下来 行,每行2个整数,代表有树的格子的横纵坐标,保证任意两个树格子不相同
输出一个正整数代表牛棚的最大边长
8 3
2 2
2 6
6 3
5