ZeroJudge K731: 路徑偵測

題目敘述

每筆測資第一行有一個正整數N，接下來會有N行，每行會有兩個整數代表x和y座標。最一開始的座標為(0, 0)，方向向右，只會有往左右走和往上下走的情況出現，不會有斜著走的情況出現。要求輸出走了N個點之後的左轉、右轉、和迴轉的次數。

範例輸入 #1

2

2 0

2 1

範例輸出 #1

1 0 0

範例輸入 #2

9  

4 0

4 9

4 8

4 10

4 2

4 3

6 3

6 10

6 9

範例輸出 #2

2 1 5

解題思路

可以邊收資料邊做計算，判斷x和y的值和目前位置是增加還是減少來判斷要怎麼轉彎或者不用轉彎。

解題程式碼如下 (僅供參考)：

#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";
}