#HDR003A. 「MCOI-06」Flight

「MCOI-06」Flight

题目描述

书虫需要移动他的盾构机

书虫将 MC 空间抽象为二维平面。他的盾构机现在在 (a,b)(a,b),而书虫想把盾构机移动到 (c,d)(c,d)

书虫每一步可以将盾构机向东南西北任何方向行动。但是这盾构机有一个限制:相邻两步不能向同一个方走!

给定 (a,b)(a,b)(c,d)(c,d),请计算书虫最少需要几步将盾构机移动到终点。

求书虫的最少步数。可以证明,他永远可以到达终点。

输入格式

本题有多组数据。

第一行一个正整数 TT,表示表示数据的组数。

接下来 TT 行,每行四个整数 a,b,c,da,b,c,d,代表一组数据,其中 (a,b)(a,b) 为起点,(c,d)(c,d) 为终点。

输出格式

输出 TT 行,第 ii 行代表第 ii 组数据的答案。

3
-2 0 -2 1
0 1 3 3
-1 1 1 1
1
5
4

样例 1 解释

  • 对于第一组,最优策略为 (2,0)(2,1)(-2,0)\rarr(-2,1)
  • 对于第二组,最优策略为 (0,1)(1,1)(1,2)(2,2)(2,3)(3,3)(0,1)\rarr(1,1)\rarr(1,2)\rarr(2,2)\rarr(2,3)\rarr(3,3)
  • 对于第三组,最优策略之一为 (1,1)(0,1)(0,0)(1,0)(1,1)(-1,1)\rarr (0,1)\rarr(0,0)\rarr(1,0)\rarr(1,1)

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(29 pts):0a,b,c,d30\le a,b,c,d\le 3
  • Subtask 2(29 pts):a=ca=c
  • Subtask 3(42 pts):无特殊限制。

对于所有数据,1T1051\le T\le 10^5a,b,c,d1018|a|,|b|,|c|,|d|\le10^{18}