QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#850515 | #7334. Endgame | Kazemaru | AC ✓ | 412ms | 147904kb | C++23 | 1.5kb | 2025-01-10 09:46:59 | 2025-01-10 09:47:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
const int N=2e6;
vector<int>q[N];queue<int>Q;
int a[N],c[N],d[N],f[N];char e[9][9];
#define o(x)||!x||x>8
#define d(i,j)max(abs(x##i-x##j),abs(y##i-y##j))
#define rto(x,y)((x3==x&&y3!=y&&(x1!=x||(y1!=y&&((y3<y1)^(y>y1)))))||(y3==y&&x3!=x&&(y1!=y||(x1!=x&&((x3<x1)^(x>x1))))))
#define uv f(u,-1,1)f(v,-1,1)if(u||v)add
#define mz(p,q)f(z,1,8)if(rto(p,q))add(x1,y1,x2,y2,p,q)
#define add(z...)if(y=dfs(z,!p))q[y].push_back(x),++d[x]
int dfs(int x1,int y1,int x2,int y2,int x3,int y3,int p){
if(d(1,2)<2||!d(1,3)||(!p&&rto(x2,y2))||(p&&d(2,3)<2&&d(1,3)>1)o(x1)o(y1)o(x2)o(y2))return 0;
int S=p*531441+x1*59049+y1*6561+x2*729+y2*81+x3*9+y3;
if(f[S])return f[S];int x=f[S]=++l,y;a[x]=p;
if(p)goto P;
uv(x1+u,y1+v,x2,y2,x3,y3);
mz(z,y3);mz(x3,z);
return x;
P:;
uv(x1,y1,x2+u,y2+v,x3,y3);
if(!d[x]&&!rto(x2,y2))return f[S]=0;
return x;
}
inline void ycl(){
dfs(2,2,4,4,6,6,0);
f(i,1,l)if(!d[i])Q.push(i);
for(;Q.size();Q.pop()){
int x=Q.front();
for(int y:q[x]){
if(a[x])d[y]=min(d[y],1ll);
if(!--d[y])c[y]=c[x]+a[x],Q.push(y);
}
}
}
inline void doing(){
f(i,1,8)scanf("%s",e[i]+1);
int x1,y1,x2,y2,x3,y3;
f(i,1,8)f(j,1,8){
if(e[i][j]=='W')x1=i,y1=j;
if(e[i][j]=='B')x2=i,y2=j;
if(e[i][j]=='R')x3=i,y3=j;
}
cout<<c[dfs(x1,y1,x2,y2,x3,y3,0)]<<"\n";
}
signed main(){
int t;
cin>>t;
ycl();
while(t--)doing();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 367ms
memory: 142448kb
input:
2 ........ ........ ........ ........ ........ .......W R....... .......B ....B... ........ ..W..... ........ .....R.. ........ ........ ........
output:
1 2
result:
ok 2 number(s): "1 2"
Test #2:
score: 0
Accepted
time: 378ms
memory: 147888kb
input:
10 ........ ........ ........ ..R..... ....W... ........ .B...... ........ .......B ........ ...R.... ........ ........ ........ W....... ........ ........ .W...B.. ........ ........ ..R..... ........ ........ ........ .W...R.. ........ ........ ........ ......B. ........ ........ ........ ........
output:
7 10 9 11 11 12 11 12 14 7
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 389ms
memory: 142180kb
input:
10 ........ ...B.... ........ ......R. ........ ........ ..W..... ........ W....B.. ........ ........ ........ .R...... ........ ........ ........ ....R... ........ ..B..... ........ ........ ........ ........ .....W.. .R...... ........ ........ ........ ..B..... ........ ........ W....... ........
output:
12 9 14 13 7 7 11 13 7 7
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 371ms
memory: 143440kb
input:
10 ..B..... ........ ..W.R... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..W..... ...R.... ..B..... ........ ........ ..R..... ........ ........ ..W..... ........ ..B..... ..B..... ...R.... W....... ........ ........ ........ ........ ........ B.......
output:
1 3 3 6 2 16 16 13 7 13
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 388ms
memory: 143496kb
input:
10 .R...... ..W..B.. ........ ........ ........ ........ ........ ........ ........ ........ ......W. ........ ........ ........ ...B.... ....R... ....W... ........ .......B ........ .....R.. ........ ........ ........ ........ ........ ........ ........ .......R ....B... ........ .W...... ........
output:
8 12 9 10 11 11 14 10 7 14
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 412ms
memory: 145800kb
input:
10 ........ ......W. ........ ..R..... ...B.... ........ ........ ........ ........ ........ ........ ........ ....R... .......B ...W.... ........ ........ ...B.... ........ ........ ........ ........ ......W. .....R.. W....... ........ ..B..... ........ ........ ........ .R...... ........ ........
output:
15 6 13 14 11 10 13 12 7 11
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 406ms
memory: 142392kb
input:
10 ........ ..W..... ....R... ........ ........ B....... ........ ........ ........ ........ ...W.... .......B ........ .R...... ........ ........ ........ ........ W......R ........ ........ ........ B....... ........ ........ ........ ........ ........ R....W.. ........ ...B.... ........ ........
output:
8 8 6 10 8 15 4 6 10 11
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 395ms
memory: 145292kb
input:
10 ........ ...B.... ........ ........ ........ R....... ...W.... ........ ....B... ........ .....R.. ..W..... ........ ........ ........ ........ R...W... ........ ........ ........ ........ .B...... ........ ........ ........ ........ ........ .......W ........ .....R.. ......B. ........ ........
output:
12 2 12 5 14 5 1 11 10 8
result:
ok 10 numbers
Test #9:
score: 0
Accepted
time: 382ms
memory: 147904kb
input:
10 ....B... ........ ..W..... .......R ........ ........ ........ ........ ........ ........ ..W..... ........ R....... ........ ........ ......B. .....R.. ........ ........ .......B ........ ........ ........ .......W ........ .W...... ........ ........ ........ ..R..... .B...... ........ .B......
output:
7 9 9 9 5 12 13 7 9 14
result:
ok 10 numbers