额，注意到 \(n=1\) 的情况，这样是一条线了。

然后有如下结论，若最后可留下 \(l\sim r\) 与可留下 \(1\sim r\) 和 \(n\sim l\) 等价，易证。

然后可以 Hash+二分找最大回文子串，再从后向前贪心做。

然后考虑到横竖互不干扰，于是只用分别求再乘起来就行了，于是可以考虑将每行/列 Hash 起来，然后和 \(n=1\) 一样做就行了。