这篇文章上次修改于 473 天前,可能其部分内容已经发生变化,如有疑问可询问作者。
本文共 1261 个字,阅读时长 ≈ 4 分钟

题目链接

这是一道隐藏的很深的结论题好像只是因为我太弱,我一开始看时以为是个模拟,然后看到数据范围之后我傻了。
怎么办呢?我们要坚信暴力出奇迹,打表出省一画图可以解决一切问题。

于是这个图就出来了

图1

然后根据玄学手推可以推出最短路是这个样子的

图1最短路

由此我们可以得到一种情况,也就是当a=b且c=d时两点间的最短路为两点的曼哈顿距离,公式为$|x_1-x_2|+|y_1-y_2|$。敲黑板!曼哈顿距离是本题解题的关键

但是毒瘤大犇出题人怎么可能这么轻易地就放过我们呢。

于是我们可以通过第一种情况延伸出剩下两种情况

abcd形成一个长方形的

图2

a=c的(Subtask2)

图3

这里就会有人问了,诶诶你不是说从第一个延伸出来的吗,怎么看着跟第一个一点关系都没有呢?不要着急,等我把这两种情况的最短路画出来你就知道了

第二种情况

图2最短路

第三种情况

图3最短路

我们可以把第二种情况看做先把cd所在的那一行当成正方形的底,然后走一遍情况一,再直走走到点cd

图2最短路2

直走我们用的方法是这个样子的,因为题目要求不能连续往同一个方向走,而这样走可以被证明每一步是最短的

直走

按这样直走,我们可以算出直走所需要的的步数,但是这里需要分类讨论(此处为本题巨坑,本蒟蒻卡在这里调了两个多小时),一种是两点的距离为偶数,一种是两点的距离是奇数。

两点的距离是偶数时,步数为两点的距离乘以二,因为每走一步之后需要重置方向,要往上或往下再走一步。

两点的距离是奇数时,步数为两点的距离乘以二减一,因为走最后一步时不需要再重置方向了,所以要减去多的一步(斜线划分步数)

因为当我们从点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;
}