2365: 最短时间
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：32
解决：19
题目描述
给定一个 N×M 的方格矩阵，其中第 i 行第 j 列的方格表示为 (i,j)（行、列下标均从 1 开始）。
初始时，每个方格中都站着一个人。
方格中的人可以沿上下左右四个方向进行移动。
已知，一个位于方格 (i,j) 的人经过一秒的移动，可以移动至 (i−1,j) 或 (i+1,j) 或 (i,j−1) 或 (i,j+1)（如果该方格确实存在的话）。
现在，给定一个目标方格 (r,c)，要求所有人同时开始行动，并以最佳行进方式赶往目标方格。
请问，所有人都成功抵达目标方格，所需花费的最短时间是多少秒。
注意，同一时间同一方格内可以存在多个人。
初始时，每个方格中都站着一个人。
方格中的人可以沿上下左右四个方向进行移动。
已知，一个位于方格 (i,j) 的人经过一秒的移动，可以移动至 (i−1,j) 或 (i+1,j) 或 (i,j−1) 或 (i,j+1)（如果该方格确实存在的话）。
现在，给定一个目标方格 (r,c)，要求所有人同时开始行动，并以最佳行进方式赶往目标方格。
请问，所有人都成功抵达目标方格，所需花费的最短时间是多少秒。
注意，同一时间同一方格内可以存在多个人。
输入
第一行包含整数 T，表示共有 T 组测试数据。
每组数据占一行，包含四个空格隔开的整数 n,m,r,c。
每组数据占一行，包含四个空格隔开的整数 n,m,r,c。
输出
每组数据输出一行结果，表示所需花费的最短时间。
样例输入 复制
3
10 10 1 1
3 5 2 4
10 2 5 1样例输出 复制
18
4
6提示
数据范围：
对于前三个测试点，1≤r≤n≤10,1≤c≤m≤10。
对于全部测试点，1≤T≤104,1≤r≤n≤109,1≤c≤m≤109。
对于前三个测试点，1≤r≤n≤10,1≤c≤m≤10。
对于全部测试点，1≤T≤104,1≤r≤n≤109,1≤c≤m≤109。