题解：P15074 [ICPC 2024 Chengdu R] Chinese Chess
C. Chinese Chess
一年前我居然还会写这种神人题目。
my blog
处理出两两点间不同种棋的最短路。发现询问次数
枚举量非常少，写出来就能过。
#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define db double
using namespace std;
const int inf=1e18;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
return x*f;
}
bool Mbe;
char opt[7];
int p;
const int maxn=95;
int n=10,m=9;
pii a[maxn];
queue<int> q;
int dis[6][maxn][maxn];
int id(int u,int v){return u*m+v;}
pii get(int id){return {id/m,id%m};}
int fxs[4][2]={{1,-1},{1,1},{-1,1},{-1,-1}};
int fxm[8][2]={{1,-2},{1,2},{-1,2},{-1,-2},{2,-1},{2,1},{-2,1},{-2,-1}};
int fxx[4][2]={{2,-2},{2,2},{-2,2},{-2,-2}};
vector<pii> op1[25],op2[25];
int op[25];
bool check1(int s1,vector<pii> que){
for(int i=0;i<=20;i++)op[i]=-1;
bool fl=1;
for(auto[i,j]:que){
int s=id(a[i].fi,a[i].se);
int d=dis[j][s][s1];
if(op[d]!=-1&&op[d]!=j){fl=0;break;}
op[d]=j;
}
return fl;
}
int ans1[maxn],ans2[maxn];
bool check2(int s1,vector<pii> que){
for(int i=0;i<=20;i++)op1[i].clear();
for(auto[i,j]:que){
int s=id(a[i].fi,a[i].se);
int d=dis[j][s][s1];
op1[d].pb({i,j});
}
bool fl=1;
for(int i=0;i<=20;i++)if(op1[i].size()){
bool fl1=0;
for(int s=0;s<n*m;s++){
if(check1(s,op1[i])){
ans1[i]=s;
fl1=1;break;
}
}
if(!fl1){fl=0;break;}
}
return fl;
}
bool check3(int s1,vector<pii> que){
for(int i=0;i<=20;i++)op2[i].clear();
for(auto[i,j]:que){
int s=id(a[i].fi,a[i].se);
int d=dis[j][s][s1];
op2[d].pb({i,j});
}
bool fl=1;
for(int i=0;i<=20;i++)if(op2[i].size()){
bool fl1=0;
for(int s=0;s<n*m;s++){
if(check2(s,op2[i])){
ans2[i]=s;
fl1=1;break;
}
}
if(!fl1){fl=0;break;}
}
return fl;
}
void work(){
p=read();
for(int i=1;i<=p;i++)a[i]={read(),read()};
opt[0]='J',opt[1]='S',opt[2]='C',opt[3]='M',opt[4]='X',opt[5]='B';
mems(dis,-1);mems(op,-1);
for(int s=0;s<n*m;s++){
for(int t=0;t<n*m;t++){
int u=get(s).fi,v=get(s).se,nx=get(t).fi,ny=get(t).se;
dis[0][s][t]=abs(u-nx)+abs(v-ny);
}
dis[1][s][s]=0,q.push(s);
while(!q.empty()){
int ss=q.front();q.pop();
int u=get(ss).fi,v=get(ss).se;
for(int i=0;i<4;i++){
int nx=u+fxs[i][0],ny=v+fxs[i][1];
if(nx<0||ny<0||nx>=n||ny>=m||dis[1][s][id(nx,ny)]!=-1)continue;
dis[1][s][id(nx,ny)]=dis[1][s][ss]+1,q.push(id(nx,ny));
}
}
for(int t=0;t<n*m;t++){
int u=get(s).fi,v=get(s).se,nx=get(t).fi,ny=get(t).se;
dis[2][s][t]=(u!=nx)+(v!=ny);
}
dis[3][s][s]=0,q.push(s);
while(!q.empty()){
int ss=q.front();q.pop();
int u=get(ss).fi,v=get(ss).se;
for(int i=0;i<8;i++){
int nx=u+fxm[i][0],ny=v+fxm[i][1];
if(nx<0||ny<0||nx>=n||ny>=m||dis[3][s][id(nx,ny)]!=-1)continue;
dis[3][s][id(nx,ny)]=dis[3][s][ss]+1,q.push(id(nx,ny));
}
}
dis[4][s][s]=0,q.push(s);
while(!q.empty()){
int ss=q.front();q.pop();
int u=get(ss).fi,v=get(ss).se;
for(int i=0;i<4;i++){
int nx=u+fxx[i][0],ny=v+fxx[i][1];
if(nx<0||ny<0||nx>=n||ny>=m||dis[4][s][id(nx,ny)]!=-1)continue;
dis[4][s][id(nx,ny)]=dis[4][s][ss]+1,q.push(id(nx,ny));
}
}
for(int t=0;t<n*m;t++){
int u=get(s).fi,v=get(s).se,nx=get(t).fi,ny=get(t).se;
if(nx<u)dis[5][s][t]=-1;
else if(nx>4)dis[5][s][t]=abs(u-nx)+abs(v-ny);
else{
if(v==ny)dis[5][s][t]=abs(nx-u);
else dis[5][s][t]=-1;
}
}
}
for(int i=0;i<6;i++){
for(int s=0;s<=n*m;s++){
for(int t=0;t<=n*m;t++)if(dis[i][s][t]==-1)dis[i][s][t]=20;
}
}
vector<pii> que;
for(int i=1;i<=p;i++){
for(int j=0;j<6;j++)que.pb({i,j});
}
for(int s=0;s<n*m;s++){
if(check1(s,que)){
cout<<"1"<<endl;
int u=get(s).fi,v=get(s).se;
cout<<"? "<<u<<" "<<v<<endl;
int x=read();
if(x==-1)x=20;
cout<<"! "<<opt[op[x]]<<endl;
return ;
}
}
for(int s=0;s<n*m;s++){
if(check2(s,que)){
cout<<"2"<<endl;
int u=get(s).fi,v=get(s).se;
cout<<"? "<<u<<" "<<v<<endl;
int x=read();
if(x==-1)x=20;
que=op1[x];
for(int ss=0;ss<n*m;ss++){
if(check1(ss,que)){
int u=get(ss).fi,v=get(ss).se;
cout<<"? "<<u<<" "<<v<<endl;
int x=read();
if(x==-1)x=20;
cout<<"! "<<opt[op[x]]<<endl;
return ;
}
}
return ;
}
}
for(int s=0;s<n*m;s++){
if(check3(s,que)){
cout<<"3"<<endl;
int u=get(s).fi,v=get(s).se;
cout<<"? "<<u<<" "<<v<<endl;
int x=read();
if(x==-1)x=20;
que=op2[x];
for(int sss=0;sss<n*m;sss++){
if(check2(sss,que)){
int u=get(sss).fi,v=get(sss).se;
cout<<"? "<<u<<" "<<v<<endl;
int x=read();
if(x==-1)x=20;
que=op1[x];
for(int ss=0;ss<n*m;ss++){
if(check1(ss,que)){
int u=get(ss).fi,v=get(ss).se;
cout<<"? "<<u<<" "<<v<<endl;
int x=read();
if(x==-1)x=20;
cout<<"! "<<opt[op[x]]<<endl;
return ;
}
}
}
}
}
}
}
bool Med;
int T;
signed main(){
T=1;
while(T--)work();
}