样例如图

#include <iostream>
#include <string>
#include <cmath>
using namespace std;string input[2010];
int lt[2010][2010];
int up[2010][2010];int Find(int n,int m)
{int Max=1;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(i==0&&j==0){lt[i][j]=1;up[i][j]=1;}else if(i==0){up[i][j]=1;if(input[i][j]==input[i][j-1]){lt[i][j]=lt[i][j-1]+1;}else{lt[i][j]=1;}}else if(j==0){lt[i][j]=1;if(input[i][j]==input[i-1][j]){up[i][j]=up[i-1][j]+1;}else{up[i][j]=1;}}else{if(input[i][j]==input[i][j-1]&&input[i][j]==input[i-1][j-1]){lt[i][j]=min(lt[i][j-1],lt[i-1][j-1])+1;}else{lt[i][j]=1;}if(input[i][j]==input[i-1][j]&&input[i][j]==input[i-1][j-1]){up[i][j]=min(up[i-1][j],up[i-1][j-1])+1;}else{up[i][j]=1;}}Max=max(Max,min(lt[i][j],up[i][j]));}}return Max;
}int main()
{freopen("rectancut.txt","r",stdin);int T;int n,m;cin>>T;for(int i=0;i<T;i++){cin>>n>>m;for(int j=0;j<n;j++){cin>>input[j];}int ans=Find(n,m);cout<<ans<<endl;	}}

这里lf 记录的是向左边延伸的最大距离，可以保证一个梯形范围内的字符相同（除了头顶的一个）
up记录的是向上延伸的最大距离，可以保证一个梯形范围内的字符相同（除了左边的一个）
当这两个取其中的最小值的时候，这个值就是正方形的边长
然后使用dp，记录最小值中的最大值，找出矩形中符合条件的最大值