P9169 [省选联考 2023] 过河卒

樱雪喵 · 2023-04-20 14:51:48 · 题解

题如其名，考场上把我送卒了。

前置知识

• bfs
• 足够的码力和耐心。

Solution

观察到 1\le n,m\le 10，可以用一个两位整数表示一个棋子的坐标。将三个棋子全部加入状态，状态数最多只有 10^6，时间上允许我们暴力搜索。

注意到状态间的转移可能成环，而在环上的状态并不一定都为平局。dfs 难以处理，我们把状态建图后使用 bfs 转移答案。

具体地，由于终止状态的胜负已知，可以从终止状态倒序转移。反过来建图，考虑类似拓扑排序的转移方式，一个点 u 可以被加入队列，当且仅当满足以下条件之一：

• 点 u 可以到达一个已确定的必败态，即 u 必胜；
• 点 u 所有可达的点状态均已确定，且全部必胜，则 u 必败。

若最后起始点的状态仍未被更新，则平局。

Tips

• 注意判两个红子不能相撞。
• 可以证明若棋子状态给定，当前局面的行动方也唯一确定。可以在第一轮 bfs 建图中记录每个局面的先后手情况，从而压掉第七维状态。
• 设两枚红子为 (a,b),(c,d)，显然它们等价，可以钦定 a\le c 以减小一倍常数。
• 似乎直接写并不卡常，所以代码没加上述第三条优化（
• 一定要全部想清楚再开始写。

Code

#include<bits/stdc++.h>
#define il inline
using namespace std;
il int read()
{
    int xr=0,F=1; char cr=getchar();
    while(cr<'0'||cr>'9') {if(cr=='-') F=-1;cr=getchar();}
    while(cr>='0'&&cr<='9')
        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
    return xr*F;
}
const int N=3e6+5,M=15;
int id,T,n,m;
int hsh(int a,int b,int c,int d,int x,int y) {return y+x*10+d*100+c*1000+b*10000+a*100000;}
struct edge{
    int nxt,to;
}e[N<<2];
int head[N],cnt;
il void add(int u,int v) {e[++cnt]={head[u],v};head[u]=cnt;}
int bel[N],vis[N],in[N];
struct qwq{
    int w,stp;
}ans[N];
struct node{
    int op,a,b,c,d,x,y;
};
char mp[M][M];
int dx[4]={-1,0,0,1};
int dy[4]={0,1,-1,0};
void bfs(node s,int h) //搜出所有可达状态，建图
{
    memset(vis,0,sizeof(vis)),memset(in,0,sizeof(in));
    memset(head,0,sizeof(head)),cnt=0;
    queue<node> q;
    q.push(s); vis[h]=1;
    while(!q.empty())
    {
        node nw=q.front(); q.pop();
        int op=nw.op,a=nw.a,b=nw.b,c=nw.c,d=nw.d,x=nw.x,y=nw.y;
        if(x==0||(a==x&&b==y)||(c==x&&d==y)) continue;
        int qwq=hsh(a,b,c,d,x,y);
        bel[qwq]=op;
        if(op)
        {
            for(int w=0;w<4;w++) //红棋 1 移动
            {
                int na=a+dx[w],nb=b+dy[w];
                if(na<0||na>=n||nb<0||nb>=m) continue;
                if(mp[na][nb]=='#'||(na==c&&nb==d)) continue;
                int pwp=hsh(na,nb,c,d,x,y);
                add(pwp,qwq); in[qwq]++;
                if(!vis[pwp]) vis[pwp]=1,q.push({op^1,na,nb,c,d,x,y});
            }
            for(int w=0;w<4;w++) //红棋 2 移动
            {
                int nc=c+dx[w],nd=d+dy[w];
                if(nc<0||nc>=n||nd<0||nd>=m) continue;
                if(mp[nc][nd]=='#'||(nc==a&&nd==b)) continue;
                int pwp=hsh(a,b,nc,nd,x,y);
                add(pwp,qwq); in[qwq]++;
                if(!vis[pwp]) vis[pwp]=1,q.push({op^1,a,b,nc,nd,x,y});
            }
        }
        else
        {
            for(int w=0;w<3;w++) //黑棋移动
            {
                int nx=x+dx[w],ny=y+dy[w];
                if(nx<0||nx>=n||ny<0||ny>=m||mp[nx][ny]=='#') continue;
                int pwp=hsh(a,b,c,d,nx,ny);
                add(pwp,qwq); in[qwq]++;
                if(!vis[pwp]) vis[pwp]=1,q.push({op^1,a,b,c,d,nx,ny});
            }
        }
    }
}
bool vs[N];
void solve()//拓扑转移答案
{
    memset(vs,0,sizeof(vs)),memset(ans,0,sizeof(ans));
    queue<int> q;
    for(int i=0;i<1e6;i++) 
    {
        if(vis[i]&&!in[i]) 
        {
            ans[i]={0,0},q.push(i);
            vs[i]=1;
        }
    }
    while(!q.empty())
    {
        int now=q.front(); q.pop();
        for(int i=head[now];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(ans[now].w==0)
            {
                if(!ans[v].w) ans[v].w=1,ans[v].stp=ans[now].stp+1;
                else ans[v].stp=min(ans[v].stp,ans[now].stp+1);
                if(!vs[v]) vs[v]=1,q.push(v);
            }
            else 
            {
                in[v]--;
                if(!ans[v].w) ans[v].stp=max(ans[v].stp,ans[now].stp+1);
                if(!in[v]&&!vs[v]) {vs[v]=1,q.push(v);}
            }
        }
    }
}
int main()
{
    id=read(),T=read();
    while(T--)
    {
        n=read(),m=read();
        int a=-1,b=0,c=0,d=0,x=0,y=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                cin>>mp[i][j];
                if(mp[i][j]=='X') x=i,y=j;
                else if(mp[i][j]=='O')
                {
                    if(a==-1) a=i,b=j;
                    else c=i,d=j;
                }
            }
        bfs({1,a,b,c,d,x,y},hsh(a,b,c,d,x,y));
        solve();
        qwq res=ans[hsh(a,b,c,d,x,y)];
        if(res.w) printf("Red %d\n",res.stp);
        else if(vs[hsh(a,b,c,d,x,y)]) printf("Black %d\n",res.stp);
        else printf("Tie\n");
    }
    return 0;
}