QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#202287 | #7334. Endgame | mc020207 | WA | 1225ms | 12948kb | C++17 | 5.4kb | 2023-10-05 21:30:54 | 2023-10-05 21:30:55 |
Judging History
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'