ZeroJudge K731: Path Detection

Given a two-dimensional plane with coordinates like those in mathematical two-dimensional coordinates (Y positive for north, X positive for east). The starting position is at (0, 0), followed by N coordinates. You need to move according to the order of these coordinates, ensuring only vertical or horizontal movements without diagonal movements, and the first point is guaranteed to be on the positive X-axis position (initial direction facing right).

Please output the number of left turns, right turns, and U-turns in this path.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line should contain a positive integer N. Following that, there will be N lines, each containing two positive integers x and y. It is guaranteed that the difference in coordinates between adjacent points does not exceed 100.Output three positive integers representing the number of left turns, right turns, and U-turns, respectively.
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 範例測資

Thought Process

You can perform calculations while receiving data, determining whether the values of x and y are increasing or decreasing relative to the current position to decide how to turn, or if a turn is necessary at all. Set up a Pair for the current x and y coordinates, and update these coordinates with each decision regarding the turning direction.

You can set up a string to store the current facing direction and use conditional statements (if) to determine how the direction string should change based on whether x and y are increasing or decreasing. Additionally, you can utilize a Map to keep track of how many times each turning direction has been used.

Sample Code－ZeroJudge K731: Path Detection

#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
Tags

Related Posts

Comments