题解：P17097 [ICPC 2017 Qingdao R] Hex Game

· · 题解

题意简述

在给定初始局面的 Hex 棋盘上，双方依次随机选择空格落子，白棋先手。求白棋连接上下边界和黑棋连接左右边界的概率。

解题思路

设空格数为 k。若继续完成整局游戏，白棋会占据随机排列中的第 1,3,5,\dots 个位置。因此，每个包含 w=\lceil\frac{k}{2}\rceil 个空格的白棋集合都等概率出现。

连接关系只会增加，且白色上下路径与黑色左右路径不可能同时存在。某方提前获胜后，继续填满棋盘不会改变胜者。于是只需统计最终棋盘中，白棋连通上下边界的方案数。总方案数为 \binom{k}{w}。

按从上到下、从左到右的顺序做轮廓线 DP。状态记录轮廓线上每列所属的白色连通块，其中编号 1 表示已经与上边界连通。处理一个格子时，它已处理的相邻格为左方、上方和右上方。若当前格填白，就合并对应连通块；否则清空该位置。每次转移后重新编号，使等价状态具有相同表示。

令 f_{s,c} 表示轮廓状态为 s 时的方案数。其中已有 c 个初始空格被填白。处理完棋盘后，若最后一行存在编号为 1 的位置，该方案由白棋获胜。将对应的 f_{s,w} 相加。再除以所有状态的 f_{s,w} 之和即可。

设可达轮廓状态数为 S。规范化状态需要 O(n)，并枚举至多 k 个白棋数量。时间复杂度为 O(n^2S(n+k))，空间复杂度为 O(Sk)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ull=unsigned long long;
using ld=long double;
const int N=13;
const int K=37;
using state=array<int,N>;
using num=array<ull,K>;
int n;
ull norm(state a)
{
    int cnt=2;
    int mp[16]={};
    ull res=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]>1)
        {
            if(!mp[a[i]])mp[a[i]]=cnt++;
            a[i]=mp[a[i]];
        }
        res|=(ull)a[i]<<(i*4);
    }
    return res;
}
ull trans(ull s,int r,int c,bool col)
{
    state a{};
    for(int i=0;i<n;i++)a[i]=s>>(i*4)&15;
    if(!col)
    {
        a[c]=0;
        return norm(a);
    }
    int b[3]={a[c],c?a[c-1]:0,c+1<n?a[c+1]:0};
    bool top=!r;
    int lab=0;
    for(int i:b)
    {
        if(i==1)top=1;
        else if(i&&!lab)lab=i;
    }
    if(top)lab=1;
    else if(!lab)lab=15;
    for(int i:b)
    {
        if(i&&i!=lab)
        {
            for(int j=0;j<n;j++)if(a[j]==i)a[j]=lab;
        }
    }
    a[c]=lab;
    return norm(a);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(6);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        char a[N][N];
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>a[i][j];
                cnt+=a[i][j]=='.';
            }
        }
        unordered_map<ull,num> f,g;
        f.reserve(16384);
        f[0][0]=1;
        int m=(cnt+1)/2,cur=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                g.clear();
                g.reserve(f.size()*2+1);
                for(auto &[s,v]:f)
                {
                    if(a[i][j]!='W')
                    {
                        auto &w=g[trans(s,i,j,0)];
                        for(int k=0;k<=min(cur,m);k++)w[k]+=v[k];
                    }
                    if(a[i][j]!='B')
                    {
                        int d=a[i][j]=='.';
                        auto &w=g[trans(s,i,j,1)];
                        for(int k=0;k+d<=m&&k<=cur;k++)w[k+d]+=v[k];
                    }
                }
                f.swap(g);
                cur+=a[i][j]=='.';
            }
        }
        ull sum=0,win=0;
        for(auto &[s,v]:f)
        {
            sum+=v[m];
            bool ok=0;
            for(int i=0;i<n;i++)if((s>>(i*4)&15)==1)ok=1;
            if(ok)win+=v[m];
        }
        ld ans=(ld)win/sum;
        cout<<"White "<<ans<<" Black "<<1-ans;
        cout<<'\n';
    }
    return 0;
}