P15074 || [ICPC 2024 Chengdu R] Chinese Chess

· · 题解

这是 Medium-Hard 吗。

思路

感性理解一下，虽然不同棋子的区分度很大，但几乎不能直接得到有效的结论。考虑乱搞一下。

对于每种棋子和每个起点，我们跑出最短路径。不同的状态只有 6\times90 种。然后就可以把这个最短路信息当黑盒来看了。

接下来处理最小询问次数。

猜测这个次数很小。考虑迭代加深搜索，枚举一个猜测次数上限 m，并设计一个爆搜的函数。每次问一个点，根据最短路的值分出一些子问题，然后递归判断这些子问题是否能在 m-1 次询问内问出来即可。

交互时就魔改一下这个函数，找一个最优策略即可。

注意到 A 是全集时操作次数也 \le3，因此时间复杂度 O(k\cdot d\cdot(rc)^4)，这里 k=6，d 是两点之间的最大最短路。

常数非常小，只要可以写出来代码，应该怎么写都能过的。

代码

有点丑。实际上还是很好写的。

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<random>
#include<ctime>
using namespace std;
struct P{int x,y,t;};
struct Q{int x,y;};
int n,an,dis;
int d[10][9][10][9][6];
string anu="JSCMXB";
vector<P> num;
void bfs(int sx,int sy,int t){
    for(int i=0;i<=9;i++){
        for(int j=0;j<=8;j++){
            d[sx][sy][i][j][t]=1e9;
        }
    }
    d[sx][sy][sx][sy][t]=0;
    queue<Q> q;
    q.push({sx,sy});
    vector<Q> to;
    for(int i=-2;i<=2;i++){
        for(int j=-2;j<=2;j++){
            if(t==0&&i*i+j*j==1) to.push_back({i,j});
            if(t==1&&i*i+j*j==2) to.push_back({i,j});
            if(t==3&&i*i+j*j==5) to.push_back({i,j});
            if(t==4&&i*i+j*j==8) to.push_back({i,j});
        }
    }
    if(t==2){
        for(int i=-9;i<=9;i++)
            if(i) to.push_back({i,0});
        for(int i=-8;i<=8;i++)
            if(i) to.push_back({0,i});
    }
    while(!q.empty()){
        Q c=q.front();q.pop();
        int x=c.x,y=c.y;
        if(t==5){
            if(x<=4) to={{1,0}};
            else to={{1,0},{0,1},{0,-1}};
        }
        for(auto p:to){
            int nx=x+p.x,ny=y+p.y;
            if(nx<0||ny<0||nx>9||ny>8) continue;
            if(d[sx][sy][nx][ny][t]>d[sx][sy][x][y][t]+1){
                d[sx][sy][nx][ny][t]=d[sx][sy][x][y][t]+1;
                q.push({nx,ny});
            }
        }
    }
    for(int i=0;i<=9;i++){
        for(int j=0;j<=8;j++){
            if(d[sx][sy][i][j][t]==1e9)
                d[sx][sy][i][j][t]=18;
                // 两点之间的最大最短路为 17
        }
    }
}
bool dfs(vector<P>&num,int m){
    if(num.size()<=1) return true;
    bool flag=1;
    for(auto p:num){
        if(p.t!=num[0].t) flag=0;
    }
    if(flag) return true;
    if(!m) return false;
    for(int i=0;i<=9;i++){
        for(int j=0;j<=8;j++){
            vector<P> cur[19];
            flag=1;
            for(auto p:num){
                cur[d[p.x][p.y][i][j][p.t]].push_back(p);
            }
            for(int d=0;d<=18;d++){
                flag&=dfs(cur[d],m-1);
                if(!flag) break;
            }
            if(flag) return true;
        }
    }
    return false;
}
Q dfs2(vector<P>&num,int m){
    bool flag=1;
    for(auto p:num){
        if(p.t!=num[0].t) flag=0;
    }
    if(flag) return {0,0};
    for(int i=0;i<=9;i++){
        for(int j=0;j<=8;j++){
            vector<P> cur[19];
            flag=1;
            for(auto p:num){
                cur[d[p.x][p.y][i][j][p.t]].push_back(p);
            }
            for(int d=0;d<=18;d++){
                flag&=dfs(cur[d],m-1);
                if(!flag) break;
            }
            if(flag) return {i,j};
        }
    }
    return {-1,-1};
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    for(int i=0;i<=9;i++){
        for(int j=0;j<=8;j++){
            for(int t=0;t<6;t++){
                bfs(i,j,t);
            }
        }
    }
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        for(int t=0;t<6;t++){
            num.push_back({x,y,t});
        }
    }
    while(!dfs(num,an)) an++;
    cout<<an<<endl;
    while(1){
        Q c=dfs2(num,an);
        cout<<"? "<<c.x<<" "<<c.y<<endl;
        cin>>dis;
        if(dis==-1) dis=18;
        vector<P> nw;
        for(auto p:num){
            if(d[p.x][p.y][c.x][c.y][p.t]==dis){
                nw.push_back(p);
            }
        }
        num=nw;an--;
        if(!an) break;
    }
    cout<<"! "<<anu[num[0].t]<<endl;
}