【题解】洛谷P1092[NOIP2004]虫食算 dfs
参考了大佬题解中的剪枝操作
#include<cstdio>
#include<map>
#include<cstdlib>
using namespace std;
int n,vis[27];
char s[4][27];
map<char,int>mp;
void dfs(int x,int y,int jw)//x列y行进位为jw
{
if(x==0)//竖式最左
{
if(jw)return;
for(int i=0;i<n;i++)
printf("%d%c",mp['A'+i],i==n-1?'\n':' ');
exit(0);
}
for(int i=x-1;i;i--)
{
int num1=mp[s[1][i]],num2=mp[s[2][i]],num3=mp[s[3][i]];
if(num1==-1||num2==-1||num3==-1)continue;
if((num1+num2)%n!=num3&&(num1+num2+1)%n!=num3)return;
}
if(mp[s[y][x]]==-1)
{
for(int i=n-1;i>=0;i--)
if(!vis[i])
{
if(y!=3)
{
mp[s[y][x]]=i;vis[i]=1;dfs(x,y+1,jw);vis[i]=0;mp[s[y][x]]=-1;
}
else
{
int w=mp[s[1][x]]+mp[s[2][x]]+jw;
if(w%n!=i)continue;
vis[i]=1;mp[s[3][x]]=i;dfs(x-1,1,w/n);vis[i]=0;mp[s[3][x]]=-1;
}
}
}
else
{
if(y!=3)dfs(x,y+1,jw);
else
{
int w=mp[s[1][x]]+mp[s[2][x]]+jw;
if(w%n!=mp[s[3][x]])return;
dfs(x-1,1,w/n);
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=3;i++)
scanf("%s",s[i]+1);
for(int i=0;i<n;i++)
mp['A'+i]=-1;
dfs(n,1,0);
return 0;
}
总结
这题对剪枝要求比较高(看不懂高斯消元的做法)