萌新 95pts求助卡常/dk
查看原帖
萌新 95pts求助卡常/dk
203008
山田リョウ楼主2024/3/1 13:18
#include<stdio.h>
#include<vector>
const char ANSWER[3][6]={"Black","Red","Tie"};
char s[12][12];
struct pos{
    int x,y;
    bool operator==(const pos&o)const{return x==o.x&&y==o.y;}
    int val(){return (x-1)*10+y-1;}
};
struct state{
    pos r,b1,b2;
    bool operator==(const state&o)const{return r==o.r&&b1==o.b1&&b2==o.b2;}
    state next(int op){
        state u=*this;
        switch(op){
            case 1:--u.r.x;break;
            case 2:--u.r.y;break;
            case 3:++u.r.y;break;
            case 4:--u.b1.x;break;
            case 5:++u.b1.x;break;
            case 6:--u.b1.y;break;
            case 7:++u.b1.y;break;
            case 8:--u.b2.x;break;
            case 9:++u.b2.x;break;
            case 10:--u.b2.y;break;
            default:++u.b2.y;
        }return u;
    }
    int val(){return r.val()*10000+b1.val()*100+b2.val();}
};
bool check(state u){
    if(s[u.r.x][u.r.y]=='#'||s[u.b1.x][u.b1.y]=='#'||s[u.b2.x][u.b2.y]=='#')return 0;
    if(u.b1==u.b2)return 0;
    return 1;
}
struct node{
    state s;int o,d,win,dis;
    std::vector<int>edge;
}a[1000000];
int mp[1000000],tot,q[1000000];
int newnode(state s,int o){
    if(~mp[s.val()])return mp[s.val()];
    return mp[s.val()]=tot,a[tot].s=s,a[tot].o=o,a[tot].d=0,a[tot].edge.clear(),tot++;
}
void work(){
    int n,m;
    pos r,b1={0,0},b2;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf(" %s",s[i]+1);
    for(int i=0;i<=m+1;++i)s[0][i]=s[n+1][i]='#';
    for(int i=1;i<=n;++i)s[i][0]=s[i][m+1]='#';
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            if(s[i][j]=='X')r={i,j},s[i][j]='.';
            else if(s[i][j]=='O'){
                if(b1.x)b2={i,j};
                else b1={i,j};
                s[i][j]='.';
            }
        }
    for(int i=0;i<tot;++i)mp[a[i].s.val()]=-1;
    tot=0;
    for(int i=newnode({r,b1,b2},0),L,R;i<tot;++i){
        if(a[i].s.r.x==1||a[i].s.r==a[i].s.b1||a[i].s.r==a[i].s.b2)continue;
        state s;
        if(a[i].o){
            s=a[i].s;
            --s.r.x;
            if(check(s))
                ++a[i].d,a[newnode(s,a[i].o^1)].edge.push_back(i);
            s=a[i].s;
            --s.r.y;
            if(check(s))
                ++a[i].d,a[newnode(s,a[i].o^1)].edge.push_back(i);
            s=a[i].s;
            ++s.r.y;
            if(check(s))
                ++a[i].d,a[newnode(s,a[i].o^1)].edge.push_back(i);
        }else{
            s=a[i].s;
            --s.b1.x;
            if(check(s))
                ++a[i].d,a[newnode(s,a[i].o^1)].edge.push_back(i);
            s=a[i].s;
            ++s.b1.x;
            if(check(s))
                ++a[i].d,a[newnode(s,a[i].o^1)].edge.push_back(i);
            s=a[i].s;
            --s.b1.y;
            if(check(s))
                ++a[i].d,a[newnode(s,a[i].o^1)].edge.push_back(i);
            s=a[i].s;
            ++s.b1.y;
            if(check(s))
                ++a[i].d,a[newnode(s,a[i].o^1)].edge.push_back(i);
            s=a[i].s;
            --s.b2.x;
            if(check(s))
                ++a[i].d,a[newnode(s,a[i].o^1)].edge.push_back(i);
            s=a[i].s;
            ++s.b2.x;
            if(check(s))
                ++a[i].d,a[newnode(s,a[i].o^1)].edge.push_back(i);
            s=a[i].s;
            --s.b2.y;
            if(check(s))
                ++a[i].d,a[newnode(s,a[i].o^1)].edge.push_back(i);
            s=a[i].s;
            ++s.b2.y;
            if(check(s))
                ++a[i].d,a[newnode(s,a[i].o^1)].edge.push_back(i);
        }
    }
    int fr=0,tl=0;
    for(int i=0;i<tot;++i)if(!a[i].d)q[tl++]=i,a[i].win=a[i].dis=0;
    for(int u;fr<tl;){
        u=q[fr++];
        if(!u)return (void)(printf("%s %d\n",ANSWER[a[u].win],a[u].dis));
        if(a[u].win){
            for(const auto&v:a[u].edge)
                if(a[v].d&&!(--a[v].d))
                    a[v].win=0,a[v].dis=a[u].dis+1,q[tl++]=v;
        }else{
            for(const auto&v:a[u].edge)
                if(a[v].d)
                    a[v].d=0,a[v].win=1,a[v].dis=a[u].dis+1,q[tl++]=v;
        }
    }
    puts(ANSWER[2]);
}
int main(){
    // freopen("zu.in","r",stdin),freopen("zu.out","w",stdout);
    for(int i=0;i<1000000;++i)mp[i]=-1;
    int t;
    for(scanf("%*d%d",&t);t--;work());
    return 0;
}
2024/3/1 13:18
加载中...