网站后台添加,合肥企业展厅设计公司,小程序软件定制开发,襄阳市网站搭建公司题干#xff1a;
给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。
输入描述:
第一行两个整数n, m代表矩阵的长和宽#xff1b;
接下来n行#xff0c;每行m个字符#xff08;小写字母#xff…题干
给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。
输入描述:
第一行两个整数n, m代表矩阵的长和宽
接下来n行每行m个字符小写字母表示矩阵
输出描述:
输出一个整数表示满足条件的最大正方形的边长。
示例1
输入
复制
5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl
输出
复制
3
备注:
对于30%的数据n,m≤100
对于100%的数据n,m≤500
解题报告 非常恶心的字符串Hash琢磨了半天才看明白、、这种前缀的是需要去模数的
AC代码
//#includecstdio
//#includeiostream
//#includealgorithm
//#includequeue
//#includemap
//#includevector
//#includeset
//#includestring
//#includecmath
//#includecstring
//using namespace std;
//typedef unsigned long long ull;
//typedef pairint,intP;
//#define maxn 505
//int n,m;
//char s[maxn][maxn];
//ull h[maxn][maxn],b[maxn*maxn],base10007,hhh[maxn][maxn];
//inline int ID(int i,int j) {
// return (i-1)*mj;
//}
//inline bool check(int mid) {
// mapull,intM;
// for(int x1; xn-mid1; x)
// for(int y1; ym-mid1; y) {
// int xxxmid-1,yyymid-1;
// ull val(h[xx][yy]-h[xx][y-1]-h[x-1][yy]h[x-1][y-1])*b[(n-x)*mm-y];
// if(M.find(val)!M.end())return 1;
// M[val]1;
// }
// return 0;
//}
//int main() {
// scanf(%d%d,n,m);
// for(int i1; in; i)scanf(%s,s[i]1);
// b[0]1;
// for(int i1; in; i)
// for(int j1; jm; j) {
// h[i][j]h[i][j-1]b[ID(i,j-1)]*(s[i][j]-a);
// b[ID(i,j)]b[ID(i,j-1)]*base;
// }for(int j1; jm; j)for(int i1; in; i)h[i][j]h[i-1][j];
// int l0,rmin(n,m),mid,ans0;
// while(lr) {
// mid(lr)/2;
// if(check(mid))ansmid,lmid1;
// else rmid-1;
// }
// printf(%d\n,ans);
// return 0;
//}#includecstdio
#includealgorithm
#define N 510
using namespace std;
typedef unsigned long long ll;
const ll D197,D2131;
int n,m,i,j,l,r,mid,ans,t;
char a[N][N];
ll pow1[N],pow2[N],h[N][N],tmp,Hash[N*N];
bool check(int x) {t0;for(i1; in; i) {for(tmp0,j1; jx; j) tmptmp*D1a[i][j],h[i][j]0;for(jx; jm; j) h[i][j]tmptmp*D1-pow1[x]*a[i][j-x]a[i][j];}for(t0,ix; im; i) {for(tmp0,j1; jx; j) tmptmp*D2h[j][i];for(jx; jn; j) Hash[t]tmptmp*D2-pow2[x]*h[j-x][i]h[j][i];} sort(Hash,Hasht);for(i1; it; i) {if(Hash[i-1]Hash[i])return 1;}return 0;
}
int main()
{scanf(%d%d,n,m);for(i1; in; i) {scanf(%s,a[i]1);for(j1; jm; j) {a[i][j]-a;}}l1,rmin(n,m);pow1[0]pow2[0]1;for(i1; in; i) pow1[i]pow1[i-1]*D1;for(i1; im; i) pow2[i]pow2[i-1]*D2;while(lr) {mid(lr)1;if(check(mid)) lmid1,ansmid;else rmid-1; }printf(%d,ans);return 0;
}
AC代码3还是这种二维Hash看得懂一点
#includebits/stdc.h
using namespace std;
typedef unsigned long long ull;
const int maxn2e610;
const ull base1131,base2233; //base基数int n, m;
char mp[510][510];
ull has[510][510];
ull p1[510], p2[510];
mapull, int mmp;void init()
{p1[0] p2[0] 1;for(int i 1; i 505; i ){p1[i] p1[i-1]*base1;p2[i] p2[i-1]*base2;}
}void Hash()
{has[0][0] 0;has[0][1] 0;has[1][0] 0;for(int i 1; i n; i ){for(int j 1; j m; j ){has[i][j] has[i][j-1]*base1 mp[i][j] - a;}}for(int i 1; i n; i){for(int j 1; j m; j ){has[i][j] has[i-1][j]*base2 has[i][j];}}
}bool check(int x)
{mmp.clear();for(int i x; i n; i ){for(int j x; j m; j ){ull k has[i][j] - has[i-x][j]*p2[x] - has[i][j-x]*p1[x] has[i-x][j-x]*p1[x]*p2[x];mmp[k] ;if(mmp[k] 2)return true;}}return false;
}int main()
{init();while(~scanf(%d%d, n, m)){for(int i 1; i n; i ){scanf(%s, mp[i]1);}Hash();int l 0, r 600, ans 0;while(l r){int mid (lr)/2;if(check(mid)){l mid1;ans mid;}else{r mid-1;}}printf(%d\n, ans);}return 0;
}
