贪心
算法思路
求N * M方阵中距离给定点(r,c)的最大曼哈顿距离.
贪心求解,可以把N * M方阵划分为四个部分,可以发现四个角是各部分的最大曼哈顿距离.
在计算时实际上求的是max( |x-r| + |y-c| ) 可以独立求两个坐标的最大值(Y总代码简洁呀)
时间复杂度
O(1)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, r, c;
int main()
{
int T;
cin >> T;
while( T-- )
{
cin >> n >> m >> r >> c;
cout << max( r - 1, n - r ) + max( c - 1, m - c ) << endl;
}
return 0;
}