暴力搜索。。表示写的有点挫= =。时间花的好多。。一共有九种转换的方法,由于转换四次的话又会转换回到初始状态。所以枚举每个方法转换[0,3]次,然后再写两个函数判断旋转的过程。。记得回溯的时候需要将状态回到上一层。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;
char cmd[][10]={"ABDE","ABC","BCEF","ADG","BDEFH","CFI",
                "DEGH","GHI","EFHI"};
int ans[2000],a[20],b[2000]={0},cnt,n;
bool isok()
{
    int i;
    for(i=0;i<9;i++)
        if(!(a[i]==0||a[i]==12))
            return false;
    return true;
}
void flip(int num)
{
    int i;
    for(i=0;cmd[num][i];i++)
    {
        a[cmd[num][i]-'A']+=3;
        a[cmd[num][i]-'A']%=12;
    }
}
void resume(int num)
{
    int i;
    for(i=0;cmd[num][i];i++)
    {
        a[cmd[num][i]-'A']-=3;
        a[cmd[num][i]-'A']=(a[cmd[num][i]-'A']+12)%12;
    }
}
void dfs(int num)
{
    int i,j;
    if(isok())
    {
        for(i=0;i<cnt;i++)
            ans[i]=b[i];
        n=cnt;
        return;
    }
    if(num>8)   return;
    for(i=0;i<4;i++)
    {
        for(j=0;j<i;j++)
        {
            flip(num);
            b[cnt++]=num;
        }
        dfs(num+1);
        for(j=0;j<i;j++)
        {
            resume(num);
            cnt--;
        }
    }
}
int main()
{
    int i;
    cnt=0;
    for(i=0;i<9;i++)
        scanf("%d",&a[i]);
    dfs(0);
    printf("%d",ans[0]+1);
    for(i=1;i<n;i++)
        printf(" %d",ans[i]+1);
    printf("\n");
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation