#44. 棋盘制作

棋盘制作

Description

给你一个 $n * m$ 的棋盘,其中每一小格都是黑色或是白色,而你的任务是在保证与每一小格相邻(指有公共边)的格子颜色都不同的情况下,能从这个 $n * m$ 的棋盘中分割出来的最大的正方形棋盘和矩形棋盘的面积各是多少?

Input Format

首先第一行将输入一个正整数$t(1 \le t \le 5)$,表示共有 $t$ 组测试样例。对于每组测试样例:接下来会先输入两个正整数 $n$, $m(1\le n, m \le 2000)$,表示所给棋盘的大小,接下来的 $n$ 行包含一个 $n * m$ 的 $01$ 矩阵,表示这张矩形棋盘的颜色($0$ 表示白色,$1$ 表示黑色)。

Output Format

对于每组测试样例,输出一行。该行有两个个正整数,分别表示能分割出的最大的正方形的面积和能分割出的最大的矩形的面积。

1
3 3
1 0 1
0 1 0
1 0 0
4 6

Hint

$Note:$ 正方形和矩形可以出现重叠。

Source

Online Judge http://127.0.0.1