题目分析

这是一个组合棋子移动的最短路径问题。棋子可以混合使用多种棋子的移动方式，需要找到从起点到终点的最少步数。

算法思路

核心思想

使用分类讨论 + 预处理BFS + 数学分析的组合方法：

1. 预处理：对马和王的移动进行BFS预处理
2. 分类讨论：根据可用棋子类型分别处理
3. 数学优化：对大范围坐标使用数学公式计算

关键技术

1. 预处理BFS

void init(){
    for(int t=0;t<2;t++){  // t=0: 只马, t=1: 马+王
        memset(dis[t],63,sizeof(dis[t]));
        queue<pair<int,int> > qu;
        qu.push(make_pair(B,B));  // 中心点
        dis[t][B][B]=0;
        // BFS计算所有位置的最短距离
    }
}

2. 移动规则判断

bool check(int sx,int sy,int tx,int ty){
    if(isr&&(sx==tx||sy==ty)) return true;  // 车：同行或同列
    if(isb&&(sx+sy==tx+ty||sx-sy==tx-ty)) return true;  // 象：同对角线
    // 检查马、王、兵能否一步到达
    auto nxt=getnxt(sx,sy);
    for(auto &[x,y]:nxt) if(x==tx&&y==ty) return true;
    return false;
}

代码详解

预处理阶段

int nx[]={-2,-1,1,2,2,1,-1,-2},ny[]={1,2,2,1,-1,-2,-2,-1};  // 马移动
int kx[]={-1,0,1,1,1,0,-1,-1},ky[]={1,1,1,0,-1,-1,-1,0};    // 王移动
int dis[2][N][N];  // 预处理的距离数组

void init(){
    for(int t=0;t<2;t++){
        // BFS计算从中心点出发到所有位置的最短距离
        // t=0: 只用马移动
        // t=1: 用马+王移动
    }
}

主逻辑分类讨论

int main(){
    init();  // 预处理
    
    while(T--){
        // 解析输入，设置棋子标志
        isr=false,isb=false,isn=false,isk=false,isp=false;
        for(char c : op){
            if(c=='Q') isr=isb=true;  // 后 = 车 + 象
            else if(c=='R') isr=true;
            else if(c=='B') isb=true;
            else if(c=='N') isn=true;
            else if(c=='K') isk=true;
            else isp=true;
        }
        
        // 情况1：能否一步到达
        if(check(sx,sy,tx,ty)){
            puts("1");
            continue;
        }
        
        // 情况2：能否两步到达
        auto nxt=getnxt(sx,sy);  // 所有可能的下一步
        bool ok=(isr||(isb&&(abs(sx+tx+sy+ty)%2==0)));  // 车或象可以两步
        for(auto &[x,y]:nxt){
            if(check(x,y,tx,ty)){  // 检查两步路径
                ok=true;
                break;
            }
        }
        if(ok){
            puts("2");
            continue;
        }
        
        // 情况3：根据具体棋子组合处理
        if(isb){  // 有象
            if(isp||isn||isk) puts("3");  // 配合其他棋子三步可达
            else puts("-1");  // 只有象可能无法到达
            continue;
        }
        
        if(isn){  // 有马
            if(isk) printf("%d\n",solve(sx,sy,tx,ty,1));  // 马+王
            else if(isp) printf("%d\n",min(solve(sx,sy,tx,ty,0),solve(sx+1,sy,tx,ty,0)+1));  // 马+兵
            else printf("%d\n",solve(sx,sy,tx,ty,0));  // 只有马
            continue;
        }
        
        if(isk){  // 只有王
            printf("%d\n",max(abs(sx-tx),abs(sy-ty)));  // 切比雪夫距离
            continue;
        }
        
        if(isp){  // 只有兵
            if(sx<tx&&sy==ty) printf("%d\n",tx-sx);  // 只能向上直线移动
            else puts("-1");
            continue;
        }
        
        puts("-1");  // 无法到达
    }
}

数学优化函数

int solve(int sx,int sy,int tx,int ty,int o){
    int x=abs(sx-tx),y=abs(sy-ty);
    if(x<y) swap(x,y);
    int d=min(y,x-y);  // 数学优化减少搜索范围
    
    // 如果在预处理范围内，直接查表
    if(x+B<N&&y+B<N) return dis[o][x+B][y+B];
    
    // 数学方法估算剩余步数
    int ret=d;
    x-=d*2,y-=d;
    
    // 各种边界情况处理...
    return ret+dis[o][x+B][y+B];
}

关键优化点

1. 预处理范围优化

• 只预处理有限范围（2000×2000）
• 对大范围坐标使用数学公式缩减到预处理范围

2. 分类讨论策略

• 一步可达：直接检查
• 两步可达：枚举中间点
• 多步情况：根据棋子组合分别处理

3. 数学分析

• 马的移动有周期性，可以用数学公式计算
• 王的移动距离就是切比雪夫距离
• 车、象、后的移动有直接的数学条件

复杂度分析

• 预处理：$O(N^2)$，$N=2000$
• 每次查询：$O(1)$ 或 $O(\text{常数})$
• 总复杂度：预处理 $O(4\times10^6)$，查询 $O(q)$