ZeroJudge K731: 路徑偵測

給一個二維平面，座標如同數學的二維座標 (Ｙ正為北，Ｘ正為東)。起始位置在 (0, 0)，接下來會有 N 個座標，你需要按照這些座標點的順序移動，保證僅會垂直或水平方向上移動，不會斜向移動，且第一個點保證一定是Ｘ軸正的位置 (初始方向向右)。

請輸出這條路徑中，左轉、右轉、迴轉的個數分別為多少。

範例測資

範例輸入範例輸出
第一行輸入一個正整數 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
ZeroJudge K731 範例測資

解題思路

可以邊收資料邊做計算，判斷 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
標籤

相關文章

發佈留言