【DFS】样例没过DFS求调
查看原帖
【DFS】样例没过DFS求调
481330
sunyizhe还是MC大佬楼主2025/6/15 20:57
//程序算法:DFS
#include <bits/stdc++.h>
using namespace std;
const int N=30;

int ans[N],Ans[N],n; //ans:字母-数字 Ans:数字-字母
char s[4][N];

bool check()
{
    for(int i=1;i<=n;i++)
    {
        int x1=ans[s[1][i]-'A'];
        int x2=ans[s[2][i]-'A'];
        int x3=ans[s[3][i]-'A'];
        if(x1!=-1&&x2!=-1&&x3!=-1)
        {
            if((x1+x2)%n!=x3&&(x1+x2+1)%n!=x3)return false;
        }
    }

    return true;
}

void dfs(int dep,int t);
void dfs0(int Dep,int t,int dep);

void dfs(int dep,int t)
{
    if(dep==0)
    {
        if(t==0)
        {
            for(int i=0;i<n;i++)
                cout<<ans[i]<<' ';
            cout<<endl;
        }
        exit(0);
    }

    dfs0(dep,t,1);
}

void dfs0(int Dep,int t,int dep)
{
    if(dep==4)
    {
        int x1=ans[s[1][Dep]-'A'];
        int x2=ans[s[2][Dep]-'A'];
        int x3=ans[s[3][Dep]-'A'];
        if((x1+x2+t)%n==x3&&check())dfs(Dep-1,(x1+x2+t)/n);
        else
        {
            int &val=ans[s[dep][Dep]-'A'];
            if(val==-1)
            {
                for(int i=0;i<n;i++)
                    if(Ans[i]!=-1)
                    {
                        val=Ans[i]=i;
                        dfs0(Dep,t,dep+1);
                        val=Ans[i]=-1;
                    }
            }
            else dfs0(Dep,t,dep+1);
        }
    }
}

void fast_read()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
    
    fast_read();
    memset(ans, -1, sizeof(ans));
    memset(Ans, -1, sizeof(Ans));
    cin>>n>>(s[1]+1)>>(s[2]+1)>>(s[3]+1);

    dfs(n,0);
    return 0;
}
2025/6/15 20:57
加载中...