同題：UVa 10642 – Can You Solve It?
下面這張圖，每個圓都有一個坐標，根據笛卡爾坐標系，您可以按照以下所示的箭頭路徑從一個圓圈移動到另一個圓圈。
total_number_of_step(s)_needed = number_of_intermediate_circles_you_pass + 1
例如，要從 (0, 3) 到 (3, 0)，您必須經過兩個中間圓 (1, 2) 和 (2, 1)。 所以，在這種情況下，所需的總步數是 2 + 1 = 3。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一行為一個整數 N 代表測試資料數量 接下來 N 行，每行包含 4 個整數 x1、y1、x2、y2 (0 ≤ x1, y1, x2, y2 ≤ 100000) (x1, y1) 代表起始座標 (x2, y2) 代表目標座標 | 對於每筆測試資料，請照格式輸出是第幾筆 以及要花費的最小步數 |
| 3 0 0 0 1 0 0 1 0 0 0 0 2 | Case 1: 1 Case 2: 2 Case 3: 3 |
解題思路
如果把步數標出來的話，可以發現 Y 軸 (橫軸) 的步數是 0 –> 1 –> 3 –> 5 –> 9，以此類推。舉例來說，當 x + y 等於 2 的時候，可以發現這些點都落在 (0, 2) 這個點的斜線上，更可以發現 (1, 1) 這個點是 (0, 2) 的步數＋1，也就是其x座標。同理，(2, 0) 的步數就是 (0, 2) 的步數＋2。
可以先設定一個陣列，並將 0、1、3、6、10．．．等數字存放到 Y 座標 (橫軸) 的位置上。收資料的時候判斷 x + y 是多少就找這個位置的步數然後加上x座標的值。
範例程式碼－ZeroJudge I859: Can You Solve It?
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
vector<long long int>Chueh;
long long int count = 0, add = 0;
for (int i = 0; i<=200000; i++)
{
count += add;
Chueh.push_back(count);
add++;
}
int N;
cin >> N;
for (int i = 0; i<N; i++)
{
long long int a, b;
cin >> a >> b;
long long int start = Chueh[a+b] + a;
cin >> a >> b;
long long int finish = Chueh[a+b] + a;
cout << "Case " << i+1 << ": " << finish-start << "\n";
}
}
//ZeroJudge I859
//Dr. SeanXD