Root M Leaper 根号M的跳跃

robinyqc · 2022-10-30 11:35:28 · 题解

我的翻译！

思路

考虑广搜，棋子第一次到达某个方格用的步数就是这个方格的答案。但不要盲目地搜，需要纸上计算一下位于 (X,Y) 的棋子，如果已知目标点的横坐标 x，求目标点的纵坐标 y。下面是推导过程：

1. 求出 x 的范围。设 L=\sqrt M，因为距离为 L，x 是整数，横坐标应满足

   \hspace9ex\lceil X-L\rceil \le x \le \lfloor X+L\rfloor\hspace10ex (1)

   即

   \hspace10ex\ X-\lfloor L\rfloor \le x \le i+\lceil L\rceil\hspace10ex (2)

2. 由题意可知:

   \hspace4ex \sqrt {(X-x)^2+(Y-y)^2}=\sqrt M \hspace10ex(3) \ \ \iff (X-x)^2+(Y-y)^2=M \hspace11ex(4)

现在 M,(X-x)^2 是已知的，我们假设 \Delta=M-(X-x)^2，由 (2) 可得， \Delta \ge 0。

把 y 当成主元，求解一元二次方程 y^2-2Yy+(Y^2-\Delta)=0。

解得：

显然，若 \Delta> 0，一个 x 对应两个 y。

实际上，这个题也可以用圆的方程数形结合来考虑：目标点共圆，半径为 \sqrt M，由一个单位圆投影加平移得到。过程计算量差不多。

由于 (x,y) 是整点，应当满足 \sqrt\Delta\in\mathbb{N}_+ 且 x,y\in[1,N]，这里特判一下即可。如果不满足，就不加入广搜队列。复杂度： O(N^2\sqrt M)。实际上会低一些，因为在极限情况下，\sqrt M 远远超过方阵最远距离（对角线），可以在代码里优化到最多 O(N^3)。并且时限 2000ms，可过。

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,step;
    node(int x,int y,int step):x(x),y(y),step(step){}//构造函数
};queue<node>q;
bool check(int d){//判断Δ是否是完全平方数
    int sd=sqrt(d);
    if(sd*sd==d)return true;
    return false;
}int n,m,mp[405][405];
void Upd(int x,int y,int data){
    if(y<=n&&y>=1&&mp[x][y]==-1){
        mp[x][y]=data;
        q.push(node(x,y,data));
    }
}

signed main(){
    cin>>n>>m;
    memset(mp,-1,sizeof(mp));
    /*小技巧：初始化为-1，既可以判断是否访问，
    又可以在无法访问时报错*/
    mp[1][1]=0;
    q.push(node(1,1,0));
    while(!q.empty()){
        node h=q.front();q.pop();
        int lim=sqrt(m),i=h.x,j=h.y;//int 类型已经帮我们向下取整了
        for(int k=max(1,h.x-lim);k<=min(n,h.x+lim);k++){//max 和 min 函数帮我们逃离过大的 m 导致的问题
            int delta=m-(i-k)*(i-k);
            if(check(delta)){
                Upd(k,j+sqrt(delta),h.step+1);
                Upd(k,j-sqrt(delta),h.step+1);
            }
        }//这里的 k 相当于枚举可能的 x
    }for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            printf("%d ",mp[i][j]);
        }puts("");
    }
    return 0;
}