QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#202287#7334. Endgamemc020207WA 1225ms12948kbC++175.4kb2023-10-05 21:30:542023-10-05 21:30:55

Judging History

你现在查看的是最新测评结果

  • [2023-10-05 21:30:55]
  • 评测
  • 测评结果:WA
  • 用时:1225ms
  • 内存:12948kb
  • [2023-10-05 21:30:54]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
bool vs[10][10][10][10][10][10][2];
int ans[10][10][10][10][10][10][2];
vector<bool*> tvs;
char mp[10][10];
int id(int x,int y){return x*8+y;}
void id(int id,int &x,int &y){x=id/8,y=id%8;}
int xc[]={1,1,1,0,0,-1,-1,-1};
int yc[]={1,0,-1,1,-1,1,0,-1};
#define inf 1000000009
bool out(int x){
    if(x < 1 || x > 8) return 1;
    return 0;
}
bool under_attck(int kx, int ky, int rx, int ry){
    For(k, 0, 7) {
        int nx, ny;
        nx = kx + xc[k];
        ny = ky + yc[k];
        if(nx == rx && ny == ry) return 1;
    }
    return 0;
}
int no_where2go(int bx,int by,int wx,int wy,int rx,int ry){
    bool f = 0;
    For(k, 0, 7) {
        int nbx, nby;
        nbx = bx + xc[k];
        nby = by + yc[k];
        if(nbx == rx || nby == ry) continue;
        if(out(nbx) || out(nby)) continue;
        if(!under_attck(nbx, nby, wx, wy)) f = 1;
    }
    return !f;
}
int check(int bx,int by,int wx,int wy,int rx,int ry, int f){
    if(out(bx)||out(by)||out(wx)||out(wy)||out(rx)||out(ry)) return 0; // out
    int idb = id(bx, by), idw = id(wx, wy), idr = id(rx, ry);
    if(idb == idw || idw == idr || idb == idr) return 0; // 碰撞
    if(!f && under_attck(bx, by, rx, ry) && !under_attck(wx, wy, rx, ry)) return 0; // 送车
    if(under_attck(bx, by, wx, wy)) return 0; // 送将
    if(f && (bx == rx || by == ry)) return 0; // 送将
    if((bx == rx || by == ry) && no_where2go(bx, by, wx, wy, rx, ry)) return 2; //将杀
    else if (no_where2go(bx, by, wx, wy, rx, ry)) return 3; //逼和
    return 1;
}
bool check2(int bx,int by,int wx,int wy,int rx,int ry, int f){
    if(out(bx)||out(by)||out(wx)||out(wy)||out(rx)||out(ry)) return 0; // out
    int idb = id(bx, by), idw = id(wx, wy), idr = id(rx, ry);
    if(idb == idw || idw == idr || idb == idr) return 0; // 碰撞
    if(!f && under_attck(bx, by, rx, ry) && !under_attck(wx, wy, rx, ry)) return 0; // 送车
    if(under_attck(bx, by, wx, wy)) return 0; // 送将
    if(f && (bx == rx || by == ry)) return 0; // 送将
    return 1;
}
void INIT(){
    For(bx,1,8) For(by,1,8) For(wx,1,8) For(wy,1,8) For(rx,1,8) For(ry,1,8){
        int checkans=check(bx, by, wx, wy, rx, ry, 0);
        if (checkans==2) vs[bx][by][wx][wy][rx][ry][1]=1,ans[bx][by][wx][wy][rx][ry][1]=0;
        else if (checkans==3) vs[bx][by][wx][wy][rx][ry][1]=1,ans[bx][by][wx][wy][rx][ry][1]=inf;
    }
    while(1){
        tvs.clear();
        For(f,0,1) For(bx,1,8) For(by,1,8) For(wx,1,8) For(wy,1,8) For(rx,1,8) For(ry,1,8){
            if (vs[bx][by][wx][wy][rx][ry][f]) continue;
            if (!f){ //white move
                // move rook
                int answer=inf;
                For(i, 1, 8){
                    if (i == rx) continue;
                    if (ry == wy && (wx - rx) * (wx - i) <= 0) continue;
                    if(!check2(bx, by, wx, wy, i, ry, f)) continue;
                    if (vs[bx][by][wx][wy][i][ry][!f]) answer=min(answer,ans[bx][by][wx][wy][i][ry][!f]+1);
                }
                For(i, 1, 8){
                    if (i == ry) continue;
                    if (rx == wx && (wy - ry) * (wy - i) <= 0) continue;
                    if(!check2(bx, by, wx, wy, rx, i, f)) continue;
                    if (vs[bx][by][wx][wy][rx][i][!f]) answer=min(answer,ans[bx][by][wx][wy][rx][i][!f]+1);
                }
                // move white king
                For(k,0,7){
                    int nwx = wx + xc[k], nwy = wy + yc[k];
                    if(!check2(bx,by,nwx,nwy,rx,ry,f)) continue;
                    if (vs[bx][by][nwx][nwy][rx][ry][!f]) answer=min(answer,ans[bx][by][nwx][nwy][rx][ry][!f]+1);
                }
                if (answer!=inf){
                    ans[bx][by][wx][wy][rx][ry][f]=answer;
                    tvs.push_back(&vs[bx][by][wx][wy][rx][ry][f]);
                }
            }else{ // black move
                bool loss=1;
                int answer=0;
                For(k,0,7){
                    int nbx=bx+xc[k],nby=by+yc[k];
                    if(!check2(nbx,nby,wx,wy,rx,ry,f)) continue;
                    if (!vs[nbx][nby][wx][wy][rx][ry][!f]) {loss=0;break;}
                    answer=max(answer,ans[nbx][nby][wx][wy][rx][ry][!f]);
                }
                if(loss){
                    ans[bx][by][wx][wy][rx][ry][f]=answer;
                    tvs.push_back(&vs[bx][by][wx][wy][rx][ry][f]);
                }
            }
        }
        for (auto it:tvs) *it=1;
        if (tvs.size()==0) break;
        tvs.clear();
    }
}
void Main(){
    memset(vs,0,sizeof(vs));
    For(i,1,8) cin>>mp[i]+1;
    int bx, by, wx, wy, rx, ry, f;
    For(i,1,8){
        For(j,1,8){
            if (mp[i][j]=='B') bx = i, by = j;
            else if (mp[i][j]=='W') wx = i, wy = j;
            else if (mp[i][j]=='R') rx = i, ry = j;
        }
    }
    cout<<ans[bx][by][wx][wy][rx][ry][0]<<endl;
}
int main(){
    // int size(512<<20); // 512M
    // __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
    INIT();
    int T;cin>>T;
    while(T--) Main();
    exit(0);
}
/*
2
........
........
........
........
........
.......W
R.......
.......B

....B...
........
..W.....
........
.....R..
........
........
........

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1225ms
memory: 12948kb

input:

2
........
........
........
........
........
.......W
R.......
.......B

....B...
........
..W.....
........
.....R..
........
........
........


output:

1
2

result:

ok 2 number(s): "1 2"

Test #2:

score: -100
Wrong Answer
time: 1188ms
memory: 12468kb

input:

10
........
........
........
..R.....
....W...
........
.B......
........

.......B
........
...R....
........
........
........
W.......
........

........
.W...B..
........
........
..R.....
........
........
........

.W...R..
........
........
........
......B.
........
........
........

........

output:

7
10
9
10
11
12
10
12
12
7

result:

wrong answer 4th numbers differ - expected: '11', found: '10'