核心思路解释
条件判断
a[i][j] ^ a[i][j-1] 是异或运算,不同为1,相同为0。
题目要求形成的子矩阵满足相邻格子数字不同(其实是01棋盘色,但这里是扩展成连通块,即矩形内数字全等,但注意边界处恰好是不同数字才连接)。
实际上这段代码写成了:如果上下或左右数字不同,则它们属于同一个“可扩展矩形块”,否则是边界。
left/right 计算
先按行计算初始左右边界(基于同行的相邻不同规则),再在逐行递推时取与上一行的交集,以保证矩形上下都是相同数字。
up 计算
表示从当前格子向上相同数字(与上方数字不同)的连续长度。
矩形面积
宽 = right - left + 1,高 = up,直接相乘就是当前可能的最大矩形。
正方形 = min(宽, 高) 取平方。
注意
这个解法实际上是一个求最大全同(且上下左右相邻值均不同)矩形的变形。
原始用途常见于洛谷 P1169 / P4147 这类“最大01交错子矩阵”问题。
最后浙江是存在的