#include<bits/stdc++.h>
using namespace std;
const int N=(1<<18)+5;
bool vis[N][2][3][7];

int n,t,full;
bool die[N];
int c[3][6],x[3][6];
int s(int st,int p,int x){
    //把第 p 个人手里的第 x 张牌在 st 中标记为 0 
    return st^=1<<(p*n+x);
}
bool have(int st,int p,int x){
    //判断在 st 情况下,第 p 个人手里第 x 张牌还在不在 
    return st&(1<<(p*n+x));
}

//计算下一个人是谁
int nx(int b,int dir,int p){
    if(dir==0) b+=p;
    else b-=p;
    if(b>2) b-=3;
    if(b<0) b+=3;
    return b;
}

// 判断这张牌是否能出 
bool legal(int a,int b,int c,int d){
    return a==4||c==4||a==c||b==d;
}

// 现在的出牌情况为 st,出牌方向是 dir
// 上一个出牌的人是 lp,出的是第 lx 张牌 
bool dfs(int st,int dir,int lp,int lx){
    //若所有牌都出完了,则返回 true 
    if(st==0) return true;
    //碰到非法情况则结束(剪枝) 
    if(die[st]) return false;
    //记忆化搜索,相同状态不需要重复搜索 
    if(vis[st][dir][lp][lx]) return 0;
    vis[st][dir][lp][lx]=1;
    //获取上一张牌的信息 
    int col=c[lp][lx],num=x[lp][lx];
    //计算现在轮到谁出牌 
    int p;
    if(num!=10)//如果上一张牌不是 skip,则朝 dir 方向移动一步 
        p=nx(lp,dir,1);
    else//如果上一张牌是 skip,则朝 dir 方向移动两步 
        p=nx(lp,dir,2);
    //判断第 p 个人手里还有没有牌 
    bool flag=0;
    for(int i=0;i<n;i++)
        if(have(st,p,i))
            flag=1;
    //如果下一个人没有牌,则一直找到一个有牌的人 
    while(!flag){
        p=nx(p,dir,1);
        for(int i=0;i<n;i++)
            if(have(st,p,i))
                flag=1;
    }
    //枚举当前这个人出哪张牌 
    for(int i=0;i<n;i++){
        //如果他有这张牌,并且能打出这张牌 
        if(have(st,p,i) && legal(col,num,c[p][i],x[p][i])){
            int gost=s(st,p,i);
            int godir=dir;
            if (x[p][i]==11) godir=!godir;
            if(dfs(gost,godir,p,i))
                return true;
        }
    }
    return false;
}

void solve(){
    cin>>n;
    full=(1<<(3*n))-1; 

    //先标记所有失败的情况
    //即有一个人的牌全打完了,其他人手里不是1张牌的情况 
    for(int i=1;i<(1<<n);i++){ 
        if(i&(i-1)){
            for(int j=1;j<(1<<n);j++){
                die[i|(j<<n)]=1;
                die[i|(j<<(n+n))]=1;
                die[(i<<n)|j]=1;
                die[(i<<n)|(j<<(n+n))]=1;
                die[(i<<(n+n))|j]=1;
                die[(i<<(n+n))|(j<<n)]=1;
            }
        }
    }
    for(int i=0;i<3;i++)
        for(int j=0;j<n;j++)
            cin>>c[i][j]>>x[i][j];
    memset(vis,0,sizeof(vis));
    //枚举先向左还是向右 
    for(int i=0;i<2;i++)
        // 枚举第一张出的牌 
        for(int j=0;j<n;j++){
            if(dfs(s(full,0,j),i,0,j)){
                printf("Yes!\n");
                return;
            }
        }
    printf("No!\n");
    return;
}

int main(){
    freopen("uno.in","r",stdin);
    freopen("uno.out","w",stdout);
    cin>>t;
    while(t--)solve();
    return 0;
}

0 条评论

目前还没有评论...