P1681 Largest Square II

After finishing his schoolwork, v 神 could finally do his "real business": taking a walk with his girlfriend. One day, as they walked, they unknowingly arrived at a desolate place. Just as v 神 was about to turn back, he noticed a sign. The sign had a line of small text and a picture. The small text said: "Contact me after you find the largest alternating square in the picture, and this land will be yours." In an era of soaring housing prices, v 神 certainly did not want to miss this opportunity, so he started searching... Of course, with v 神's ability, he couldn't find it. Can you help v 神 find it?

There is a grid on the picture, consisting of $N\times M$ cells. Each cell is colored either black or white. Find a square of maximum area whose interior is black-and-white alternating, that is, any two adjacent unit cells (sharing an edge) must not have the same color.

The first line contains two integers $N$ and $M$, denoting the number of rows and columns, respectively. Then follow $N$ lines, each containing $M$ numbers. Each number is $0$ or $1$, indicating that the cell is black or white, respectively.

Output a single line containing the side length of the largest square that satisfies the condition.

Sample Explanation: The square from $(1,1)$ to $(2,2)$ satisfies the condition, and its side length is $2$. Constraints: - For $30\%$ of the testdata, $N \le 20$. - For $60\%$ of the testdata, $N \le 300$. - For $100\%$ of the testdata, $N \le 1500$. Translated by ChatGPT 5