蒟蒻求问
查看原帖
蒟蒻求问
907113
Bug_Hunter楼主2024/10/18 14:43
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,num[30];
bool flag,f[N][N];
vector<int>ans;
char ch[N][N];;
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
bool cl(string t,int i,int j){
	int len=t.size()-1;
	if(j+len-1>m) return 0;
	for(int d=1;d<=len;d++){
		if(f[i][j+d-1]) return 0;
		if(ch[i][j+d-1]!=t[d]) return 0;
	}return 1;
}
bool cr(string t,int i,int j){
	int len=t.size()-1;
	if(i+len-1>n) return 0;
	for(int d=1;d<=len;d++){
		if(f[i+d-1][j]) return 0;
		if(ch[i+d-1][j]!=t[d]) return 0;
	}return 1;
}
void work(string t,int i,int j){
	if(flag) return;
	if(f[i][j]){
		if(i==n&&j==m) flag=1;
		if(i<n) work(t,i+1,j);
		else work(t,1,j+1);
	}
	int len=t.size()-1;
	if(cl(t,i,j)){
		for(int d=1;d<=len;d++) f[i][j+d-1]=1;
		if(i<n) work(t,i+1,j);
		else work(t,1,j+1);
		for(int d=1;d<=len;d++) f[i][j+d-1]=0;
	}
	if(cr(t,i,j)){
		for(int d=1;d<=len;d++) f[i+d-1][j]=1;
		work(t,i+len-1,j);
		for(int d=1;d<=len;d++) f[i+d-1][j]=0;
	}
}
bool check(int x){
	flag=0;
	string t1=" ",t2=" ";
	if(x<=n){
		for(int i=1;i<=x;i++) t1=t1+ch[i][1];
		work(t1,1,1);
	}
	if(x<=m){
		for(int i=1;i<=x;i++) t2=t2+ch[1][i];
		work(t2,1,1);
	}
	return flag;
}
int main(){
//	freopen("print.in","r",stdin);
//	freopen("print.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ch[i][j];
			num[ch[i][j]-'a'+1]++;
		}
	}
	bool ft[N]={0};
	if(num[ch[1][1]-'a'+1]==n*m){
		for(int i=1;i*i<=max(n,m);i++){
			if(n%i==0) ft[n/i]=ft[i]=1;
			if(m%i==0) ft[m/i]=ft[i]=1;
		}
		for(int i=1;i<=max(n,m);i++) if(ft[i]) ans.push_back(i);
		sort(ans.begin(),ans.end());
		cout<<ans.size()<<"\n";
		for(int i=0;i<ans.size();i++) cout<<ans[i]<<' ';
		return 0;
	}
	int sum=num[ch[1][1]-'a'+1],gd=num[ch[1][1]-'a'+1];
	for(int i=1;i<=26;i++){
		if(i+'a'-1==ch[1][1]) continue;
		if(num[i]!=0) gd=gcd(gd,num[i]);
		sum+=num[i];
	}
	int t=sum/gd;
	for(int i=1;i*t<=max(n,m);i++){
		if(check(i*t)) ans.push_back(i*t);
	}
	cout<<ans.size()<<"\n";
	for(int i=0;i<ans.size();i++) cout<<ans[i]<<' ';
	return 0;
}
2024/10/18 14:43
加载中...