P1169 [ZJOI2007] Chessboard Making

# Description Chess is one of the oldest games in the world, as famous as China’s Go and Xiangqi and Japan’s Shogi. It is said that chess originated from the ideas of the I Ching: the board is an $8 \times 8$ checkerboard corresponding to the sixty-four hexagrams, with black and white representing yin and yang. Our protagonist `小Q` is a die-hard chess enthusiast. As a top expert, he is no longer satisfied with the standard board and rules, so he and his good friend `小W` decide to enlarge the board to suit their new rules. `小Q` finds a rectangular sheet made up of $N \times M$ square cells, each painted in one of two colors: black or white. `小Q` wants to cut out a part of this sheet to serve as the new chessboard. Of course, he wants this board to be as large as possible. However, `小Q` has not decided whether to choose a square board or a rectangular board (in either case, the board must be checkerboard-colored, i.e., adjacent cells have different colors). Therefore, he wants to find the maximum possible area of a square chessboard and the maximum possible area of a rectangular chessboard, so that he can decide which is better. Now `小Q` turns to you, who is about to participate in the National Olympiad in Informatics. Can you help him?

Chess is one of the oldest games in the world, as famous as China’s Go and Xiangqi and Japan’s Shogi. It is said that chess originated from the ideas of the I Ching: the board is an $8 \times 8$ checkerboard corresponding to the sixty-four hexagrams, with black and white representing yin and yang. Our protagonist `小Q` is a die-hard chess enthusiast. As a top expert, he is no longer satisfied with the standard board and rules, so he and his good friend `小W` decide to enlarge the board to suit their new rules. `小Q` finds a rectangular sheet made up of $N \times M$ square cells, each painted in one of two colors: black or white. `小Q` wants to cut out a part of this sheet to serve as the new chessboard. Of course, he wants this board to be as large as possible. However, `小Q` has not decided whether to choose a square board or a rectangular board (in either case, the board must be checkerboard-colored, i.e., adjacent cells have different colors). Therefore, he wants to find the maximum possible area of a square chessboard and the maximum possible area of a rectangular chessboard, so that he can decide which is better. Now `小Q` turns to you, who is about to participate in the National Olympiad in Informatics. Can you help him? # Description

The first line contains two integers $N$ and $M$, denoting the number of rows and columns of the rectangular sheet. The next $N$ lines contain a $N \times M$ $01$ matrix representing the colors ($0$ means white, $1$ means black). Each of these $N$ lines contains exactly $M$ characters without spaces.

Output two lines, each containing one integer. The first line is the area of the largest square chessboard that can be found; the second line is the area of the largest rectangular chessboard that can be found (note that the square and the rectangle may overlap or one may contain the other).

For $20\%$ of the testdata, $N, M \le 80$. For $40\%$ of the testdata, $N, M \le 400$. For $100\%$ of the testdata, $N, M \le 2000$. Translated by ChatGPT 5