i859 - 10642 - Can You Solve It?

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算從點 (x1, y1) 到點 (x2, y2) 所需的最小步數，其中每一步可以移動到相鄰的點 (x+1, y) 或 (x, y+1)。 步數定義為經過的圓圈數量加一。

解題思路

題目實際上要求計算從 (x1, y1) 到 (x2, y2) 的曼哈頓距離。 曼哈頓距離定義為 |x1 - x2| + |y1 - y2|。 然而，題目要求的是經過的圓圈數量加一，而經過的圓圈數量等於曼哈頓距離。 因此，問題簡化為計算兩個點之間的曼哈頓距離。

程式碼中，利用公式 (a+b)*(a+b+1)/2 + a 計算從 (0,0) 到 (a,b) 的路徑數量，然後計算從 (0,0) 到 (x1, y1) 和 (0,0) 到 (x2, y2) 的路徑數量之差的絕對值，即為題目要求的步數。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	long long int n,a,b,c,d;
	cin >> n;
	for(int i=1;i<=n;++i){
		cin >> a >> b >> c >> d;
		cout << "Case " << i << ": " << llabs(((a+b)*(a+b+1)/2+a)-((c+d)*(c+d+1)/2+c)) << "\n";
	}
}