P4368 [Code+#4]喵呜

· · 题解

说难也难，说易也易。

话说，审了这么多次，都是 \LaTeX 的问题，能不能确切的指明到底是哪里的错误啊……求求了

从“模拟”题签里抽出来的，当然需要模拟，但这题还有一点数学的成分。

题目说：

在一个平面直角坐标系中，给出一个坐标。

从坐标处走到 (1,1) 或 (n,1) 或 (1,n) 或 (n,n) 处的最短路径所需步数是多少，如果走不到，输出 -1 。

题一看就很奇妙，因为不是一个一个点移动，而是移动 a,b 这样的点数，那么第一个问题就是如何确定走的方向（样例1第一组数据）：

这样看的话什么也看不出来，我们要想确定一个行走的最短路径，首先必须保证它行得通。

那么根据行走的特性，我们仔细想想。

先看一个化简后的问题：

一次走两格，向哪里走能走出去？

不难看出是向右走，那么规模再大一点呢？

右边有十一个格子，左边有六个格子，明显这一次必须要向左走了。

那么，从上面的例子中可以得出，向那边走出去，那边的距离就一定要可以被步数距离整除（余数为零）。

得到了这个，确定方向就不难了：

Code1:

(!(R%a))?m[0][0]=x/a:m[0][0]=-1;//向右能走吗？能走顺便存一下步数。
(!(x%a))?m[0][1]=R/a:m[0][1]=-1;//向左能走吗？能走顺便存一下步数。
(!(U%b))?m[1][0]=y/b:m[1][0]=-1;//向上能走吗？能走顺便存一下步数。
(!(y%b))?m[1][1]=U/b:m[1][1]=-1;//向下能走吗？能走顺便存一下步数。

if 版：

if(R%a==0) m[0][0]=R/a;
else m[0][0]=-1;
if(x%a==0) m[0][0]=x/a;
else m[0][0]=-1;
if(U%a==0) m[0][0]=U/a;
else m[0][0]=-1;
if(y%a==0) m[0][0]=y/a;
else m[0][0]=-1;

以例子为例，计算后的数组长这样：

m[0][0]=1;//向右1步
m[0][1]=1;//向左1步
m[1][0]=1;//向上1步
m[1][1]=1;//向下1步

那么确定了方向，还要确定步数。

这其实是一个难点，想通了也不难 。

因为猫猫是同时向两个方向走，所以要解决两个问题。

然而没有必然联系。

以下默认 (a=2,b=1)

第一个：

我到了你没到.jpg

尴尬了,我还没到第一颗树……所以为什么我不能走开

怎么办？

我等你一下，我先回去

于是问题解决了

问题二：

我到了你却到不了

到不了？

我们不是计算了能不能到了吗？

事实上，这里的“到不了”说的是“不能同时到”。

明显看出，这边无论怎么绕，也绕不出这个圈子。

上面那个例子为什么能绕出去？

因为向左的步数给了向下的步数两个回合的斡旋时间。

向上走一次向下走一次相当于坐标没有变，所以如果想保持在某条与 x 轴或 y 轴平行的的直线上移动,两种移动的步数差定为偶数!

根据这一点,我们就可以理感性地写出一份模拟四个方向的代码:

Code2:

for(register int i=0;i<=1;i++){
        for(register int j=0;j<=1;j++){
            if((~m[0][i])&&(~m[1][j])&&(m[1][j]-m[0][i])%2==0){
                ll temp=max(m[1][j],m[0][i]);
                if(ans>temp||!(~ans)) ans=temp;
            }
        }
    }

硬性模拟版:

if((~m[0][0])&&(~m[1][0])&&(m[0][0]-m[1][0])%2==0){
    ll temp=max(m[0][0],m[1][0]);
    if(ans>temp||!(~ans)) ans=temp;
}
if((~m[0][0])&&(~m[1][1])&&(m[0][0]-m[1][1])%2==0){
    ll temp=max(m[0][0],m[1][1]);
    if(ans>temp||!(~ans)) ans=temp;
}
if((~m[0][1])&&(~m[1][0])&&(m[0][1]-m[1][0])%2==0){
    ll temp=max(m[0][1],m[1][0]);
    if(ans>temp||!(~ans)) ans=temp;
}
if((~m[0][1])&&(~m[1][1])&&(m[0][1]-m[1][1])%2==0){
    ll temp=max(m[0][1],m[1][1]);
    if(ans>temp||!(~ans)) ans=temp;
}

tips:

// ~ 运算符其实等同于！=-1

那么综合核一下。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
inline ll read(){
    long long num;char c;
    bool flag=false;
    while((c=getchar())=='\n'||c=='\r'||c==' ');
    c=='-'?flag=true:num=c^48;
    while(isdigit(c=getchar())){
        num=(num<<3)+(num<<1)+(c^48);
    }
    return (flag?-1:1)*num;
}
ll T,n,h,x,y,a,b;
ll U,R,l,r;
ll m[2][2];
void check(ll ans){
    for(register int i=0;i<=1;i++){
        for(register int j=0;j<=1;j++){
            if((~m[0][i])&&(~m[1][j])&&(m[1][j]-m[0][i])%2==0){
                ll temp=max(m[1][j],m[0][i]);
                if(ans>temp||!(~ans)) ans=temp;
            }
        }
    }
    printf("%lld\n",ans);
}
int main()
{
    T=read();
    while(T--){
        n=read(),h=read(),x=read(),y=read();
        a=read(),b=read();
        R=n-x,U=h-y;x--,y--;
        (!(x%a))?m[0][0]=x/a:m[0][0]=-1;
        (!(R%a))?m[0][1]=R/a:m[0][1]=-1;
        (!(y%b))?m[1][0]=y/b:m[1][0]=-1;
        (!(U%b))?m[1][1]=U/b:m[1][1]=-1;
        check(-1);
    }
    return 0;
}

完结撒花~