給一個二維平面,座標如同數學的二維座標 (Y正為北,X正為東)。起始位置在 (0, 0),接下來會有 N 個座標,你需要按照這些座標點的順序移動,保證僅會垂直或水平方向上移動,不會斜向移動,且第一個點保證一定是X軸正的位置 (初始方向向右)。
請輸出這條路徑中,左轉、右轉、迴轉的個數分別為多少。
範例測資
範例輸入 | 範例輸出 |
---|---|
第一行輸入一個正整數 N,接下來有 N 行,每一行都有兩個正整數 x 和 y。保證的是相鄰兩個點的座標差值不超過 100。 | 輸出三個正整數,分別代表左轉、右轉、迴轉的次數。 |
2 2 0 2 1 | 1 0 0 |
9 4 0 4 9 4 8 4 10 4 2 4 3 6 3 6 10 6 9 | 2 1 5 |
解題思路
可以邊收資料邊做計算,判斷 x 和 y 的值和目前位置是增加還是減少來判斷要怎麼轉彎或者不用轉彎。設定一個目前 x 和 y 座標的 Pair<int, int>,每一次判斷完轉彎方向就將收到的 x 和 y 設定為目前的 x 和 y 座標的 Pair。
可以設定一個字串來存目前面朝的方向,再利用 If 判斷 x 和 y 的增減來看要將方向字串變成哪一個方向,並且可以使用 Map 來紀錄每一種轉彎方式總共用了幾次。
範例程式碼-ZeroJudge K731: 路徑偵測
#include <iostream>
#include <map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
pair<int, int> start;
start.first = 0;
start.second = 0;
string direction = "right";
map<string, int>MAP;
for (int i = 0; i<N; i++)
{
int x, y;
cin >> x >> y;
if (x > start.first)
{
if (direction == "left") MAP["return"]++;
else if (direction == "up") MAP["right"]++;
else if (direction == "down") MAP["left"]++;
direction = "right";
}
else if (x < start.first)
{
if (direction == "right") MAP["return"]++;
else if (direction == "down") MAP["right"]++;
else if (direction == "up") MAP["left"]++;
direction = "left";
}
else if (y > start.second)
{
if (direction == "down") MAP["return"]++;
else if (direction == "left") MAP["right"]++;
else if (direction == "right") MAP["left"]++;
direction = "up";
}
else
{
if (direction == "up") MAP["return"]++;
else if (direction == "right") MAP["right"]++;
else if (direction == "left") MAP["left"]++;
direction = "down";
}
start.first = x;
start.second = y;
}
cout << MAP["left"] << " " << MAP["right"] << " " << MAP["return"] << "\n";
}
//ZeroJudge K731
//Dr. SeanXD