这篇文章上次修改于 473 天前,可能其部分内容已经发生变化,如有疑问可询问作者。
本文共 1261 个字,阅读时长 ≈ 4 分钟
这是一道隐藏的很深的结论题好像只是因为我太弱,我一开始看时以为是个模拟,然后看到数据范围之后我傻了。
怎么办呢?我们要坚信暴力出奇迹,打表出省一画图可以解决一切问题。
于是这个图就出来了
然后根据玄学手推可以推出最短路是这个样子的
由此我们可以得到一种情况,也就是当a=b且c=d时两点间的最短路为两点的曼哈顿距离,公式为$|x_1-x_2|+|y_1-y_2|$。敲黑板!曼哈顿距离是本题解题的关键
但是毒瘤大犇出题人怎么可能这么轻易地就放过我们呢。
于是我们可以通过第一种情况延伸出剩下两种情况
abcd形成一个长方形的
a=c的(Subtask2)
这里就会有人问了,诶诶你不是说从第一个延伸出来的吗,怎么看着跟第一个一点关系都没有呢?不要着急,等我把这两种情况的最短路画出来你就知道了
第二种情况
第三种情况
我们可以把第二种情况看做先把cd所在的那一行当成正方形的底,然后走一遍情况一,再直走走到点cd
直走我们用的方法是这个样子的,因为题目要求不能连续往同一个方向走,而这样走可以被证明每一步是最短的
按这样直走,我们可以算出直走所需要的的步数,但是这里需要分类讨论(此处为本题巨坑,本蒟蒻卡在这里调了两个多小时),一种是两点的距离为偶数,一种是两点的距离是奇数。
两点的距离是偶数时,步数为两点的距离乘以二,因为每走一步之后需要重置方向,要往上或往下再走一步。
两点的距离是奇数时,步数为两点的距离乘以二减一,因为走最后一步时不需要再重置方向了,所以要减去多的一步(斜线划分步数)
因为当我们从点ab走到正方形的右下角时,正方形的右下角和点cd在一条横轴上,所以我们直接走直线即可到达点cd,所需的步数即为从点ab走到正方形右下角的步数加从正方形右下角走直线到点cd的步数。
而情况三则比较简单,直接从点ab走直线到点cd即可。
本题最大的难点在于分类讨论和三种情况的解决,都解决后其实就是一道结论题
AC代码
#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long//反正空间够,不开long long见祖宗,而且你必须开
using namespace std;
signed main()//因为define了int,所以要改成signed
{
int T;
cin>>T;
for(int cishu=0;cishu<T;++cishu){
int a,b,c,d;
cin>>a>>b>>c>>d;
int ac=abs(a-c),bd=abs(b-d);
int temp=ac,ans=min(ac,bd);
//哪边小把哪边当做正方形的底,要不然就把点cd越过去了
ac-=min(temp,bd);//求需要直走的长度
bd-=min(temp,bd);
int bigger=max(ac,bd);
if(bigger&1) cout<<(ans*2+bigger*2-1);
//位运算判断奇偶更快
else cout<<(ans*2+bigger*2);
cout<<endl;
}
return 0;
}
没有评论