k372 - Error

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算兩個點之間的曼哈頓距離的最小值。給定八個整數 a[0] 到 a[7]，它們代表兩個點的座標：(a[0], a[1]) 和 (a[2], a[3]) 以及 (a[4], a[5]) 和 (a[6], a[7])。目標是找到這兩個點之間曼哈頓距離的最小值，即 |x1 - x2| + |y1 - y2| 的最小值。

解題思路

題目可以簡化為計算兩個點之間的曼哈頓距離，然後取最小值。具體來說，我們需要計算以下三種情況的曼哈頓距離：

1. (a[0], a[1]) 到 (a[2], a[3]) 的距離
2. (a[0], a[1]) 到 (a[6], a[7]) 的距離
3. (a[4], a[5]) 到 (a[2], a[3]) 的距離
4. (a[4], a[5]) 到 (a[6], a[7]) 的距離

然後，我們計算 (a[0], a[1]) 和 (a[4], a[5]) 之間的曼哈頓距離，以及 (a[2], a[3]) 和 (a[6], a[7]) 之間的曼哈頓距離。 對於第一個點，我們考慮以下兩種情況：

• (a[0], a[1]) 到 (a[2], a[3]) 的距離：abs(a[0] - a[2]) + abs(a[1] - a[3])
• (a[0], a[1]) 到 (a[6], a[7]) 的距離：abs(a[0] - a[6]) + abs(a[1] - a[7]) 對於第二個點，我們考慮以下兩種情況：
• (a[4], a[5]) 到 (a[2], a[3]) 的距離：abs(a[4] - a[2]) + abs(a[5] - a[3])
• (a[4], a[5]) 到 (a[6], a[7]) 的距離：abs(a[4] - a[6]) + abs(a[5] - a[7])

程式碼中，ansx 計算的是 x 座標的最小曼哈頓距離，ansy 計算的是 y 座標的最小曼哈頓距離。最後，將 ansx 和 ansy 相加得到結果。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int a[8],ansx,ansy;
int main(){
	for(int i=0;i<8;++i)
		cin >> a[i];
	ansx=min(abs(a[4]-a[6]),min(abs(a[0]-a[4])+abs(a[2]-a[6]),abs(a[0]-a[6])+abs(a[2]-a[4])));
	ansy=min(abs(a[5]-a[7]),min(abs(a[1]-a[5])+abs(a[3]-a[7]),abs(a[1]-a[7])+abs(a[3]-a[5])));
	cout << ansx+ansy;
}