自动搬运

查看原文

来自洛谷，原作者为

	Rosemary_dream Rosmarinus & Rosmontis|往世一切空梦,此刻仍如幻影

搬运于2025-08-24 21:59:26，当前版本为作者最后更新于2022-06-10 17:30:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

说难也难，说易也易。

话说，审了这么多次，都是 $\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;
}

完结撒花~