[比赛][暴力][搜索][题意] 2018 ICPC 徐州网络赛 C Cacti Lottery

比赛最后的时候三个人在看B和C，真的是紧张，根本看不懂题意，也不懂第二个样例怎么算出来的，今天看了看发现就完全是考的搜索，完 全 就 是 搜 索

能过了BC的话也算是有8个A了，没准可以进。。。可惜没如果，怪自己当时脑子进水，一脸懵逼。

两个dfs，第一个把对方知道的自己不知道的填充上，第二个把两个人都不知道的填充上，注意这里的题意，很坑，需要自己好好理解。可能是我写的太挫了，我这个码量有点大。。。
错误的话，排列写成了组合，wa了两发，意识到之后直接加了个阶乘。。懒癌。还有就是搜完一个填充点之后return之前要把那个点的状态复原。

#include

using namespace std;
const int maxn=1e5+5;
const double eps = 1e-6;
typedef long long LL;

set ns;
char ori[5][5];
int board[5][5],cnt1,cnt2,ca,cb;
int vis[10],vis1[10],vis2[10];
double ans,cur[10];
double cost[25]={0,1,2,3,4,5,10000,36,720,360,80,252,108,72,54,180,72,180,119,36,360,1080,144,1800,3600};
double C[11][11];
double ni[11];

void get_C()
{
    ni[0]=1;
    for (int i=1;i<=9;i++)
        ni[i]=i*ni[i-1];
    int m=10;
    C[0][0] = 1;
    for(int i=1;i<=m;i++)
    {
        C[i][0] = 1;
        for(int j=1;j<=i;j++)
            //C[i][j] = C[i-1][j]+C[i-1][j-1];
            C[i][j] = (C[i-1][j]+C[i-1][j-1]);
    }
}

bool check(int op,int k)
{
    if(op==1)
        return board[k][1]>0&&board[k][2]>0&&board[k][3]>0;
    if(op==2)
        return board[1][k]>0&&board[2][k]>0&&board[3][k]>0;
    if(op==3)
        return board[1][1]>0&&board[2][2]>0&&board[3][3]>0;
    if(op==4)
        return board[3][1]>0&&board[2][2]>0&&board[1][3]>0;
}

void dfs2()
{
    if(cnt2)
    {
        for (int i=1; i<=3; i++)
            for (int j=1; j<=3; j++)
            {
                if(board[i][j]==-1)
                {
                    for (set::iterator it=ns.begin(); it!=ns.end(); it++)
                        if(vis[*it]==-1)
                        {
                            board[i][j]=(*it);
                            cnt2--;
                            vis[*it]=1;
                            dfs2();
                            cnt2++;
                            vis[*it]=-1;
                        }
                    board[i][j]=-1;
                    return ;
                }
            }
    }
    else
    {
        for (int i=1;i<=3;i++)
        {
            if(!vis2[i])
                cur[i]+=cost[board[i][1]+board[i][2]+board[i][3]]/cb;
        }
        for (int i=4;i<=6;i++)
        {
            if(!vis2[i])
                cur[i]+=cost[board[1][i-3]+board[2][i-3]+board[3][i-3]]/cb;
        }
        if(!vis2[7])
            cur[7]+=cost[board[1][1]+board[2][2]+board[3][3]]/cb;
        if(!vis2[8])
            cur[8]+=cost[board[3][1]+board[2][2]+board[1][3]]/cb;
    }
}

void dfs1()
{
    if(cnt1)
    {
        for (int i=1; i<=3; i++)
            for (int j=1; j<=3; j++)
            {
                if(board[i][j]==0)
                {
                    for (set::iterator it=ns.begin(); it!=ns.end(); it++)
                        if(vis[*it]==-1)
                        {
                            board[i][j]=(*it);
                            cnt1--;
                            vis[*it]=1;
                            dfs1();
                            cnt1++;
                            vis[*it]=-1;
                        }
                    board[i][j]=0;
                    return ;
                }
            }
    }
    else
    {
        memset(cur,0,sizeof(cur));
        memset(vis2,0,sizeof(vis2));
        for (int i=1; i<=3; i++)
        {
            if(check(1,i))
            {
                cur[i]=cost[board[i][1]+board[i][2]+board[i][3]];
                vis2[i]=1;
            }
            if(check(2,i))
            {
                cur[i+3]=cost[board[1][i]+board[2][i]+board[3][i]];
                vis2[i+3]=1;
            }
        }
        if(check(3,0))
        {
            cur[7]=cost[board[1][1]+board[2][2]+board[3][3]];
            vis2[7]=1;
        }
        if(check(4,0))
        {
            cur[8]=cost[board[3][1]+board[2][2]+board[1][3]];
            vis2[8]=1;
        }
        if(cnt2)
        {
            dfs2();
        }

        double tm=0.0;
        for (int i=1;i<=8;i++)
        {
            tm=max(tm,cur[i]);
        }
        ans+=tm/ca;
    }
    return ;
}

int main()
{
    int T;
    get_C();
    scanf("%d",&T);
    while(T--)
    {
        memset(vis,-1,sizeof(vis));
        ans=0.0;
        ns.clear();
        for (int i=1; i<=9; i++)
            ns.insert(i);
        cnt1=cnt2=0;
        for (int i=1; i<=3; i++)
            scanf(" %s",ori[i]+1);
        for (int i=1; i<=3; i++)
            for (int j=1; j<=3; j++)
            {
                if(isdigit(ori[i][j]))
                {
                    board[i][j]=ori[i][j]-'0';
                    ns.erase(board[i][j]);
                    vis[board[i][j]]=1;
                }
                if(ori[i][j]=='*')
                {
                    board[i][j]=0;
                    cnt1++;
                }
                if(ori[i][j]=='#')
                {
                    board[i][j]=-1;
                    cnt2++;
                }
            }
        ca=C[cnt1+cnt2][cnt1]*ni[cnt1],cb=ni[cnt2];
        dfs1();
        printf("%.6f\n",ans);
    }
}