这道题有什么其他解法吗
查看原帖
这道题有什么其他解法吗
961149
xiao7_Mr_10_楼主2023/10/22 13:15

我的解法就是搜索,10分钟写完就过了,你们有没有更快的做法awa

#include <bits/stdc++.h>
using namespace std;
int n,a[105][105],b[105],cnt[114514],ans;
void dfs(int id,int step){
	if(step==2){
		int x=0;
		for(int i = 1;i <= 5;i++)x=x*10+a[id][i];
		cnt[x]++;
		return;
	}
	for(int i = 1;i <= 5;i++){
		for(int j = 0;j <= 9;j++){
			if(a[id][i]==j)continue;
			int last=a[id][i];
			a[id][i]=j;
			dfs(id,step+1);
			a[id][i]=last;
		}
	}
	for(int i = 1;i <= 4;i++){
		for(int j = 1;j <= 9;j++){
			if((a[id][i]+j)%10==a[id][i]&&(a[id][i+1]+j)%10==a[id][i+1])continue;
			int last=a[id][i],last1=a[id][i+1];
			a[id][i]=(a[id][i]+j)%10;
			a[id][i+1]=(a[id][i+1]+j)%10;
			dfs(id,step+1);
			a[id][i]=last,a[id][i+1]=last1;
		}
	}
}
int main(){
	cin >> n;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= 5;j++)
			cin >> a[i][j];
	for(int i = 1;i <= n;i++)dfs(i,1);
	for(int i = 0;i <= 100000;i++)
		if(cnt[i]==n)
			ans++;
	cout << ans;
	return 0;
}
2023/10/22 13:15
加载中...