526互联

335. Self Crossing (Hard)

发布时间 2023-07-28 17:03:27作者: zwyyy456

Description

335. Self Crossing (Hard)

You are given an array of integers distance.

You start at the point (0, 0) on an X-Y plane, and you move distance[0] meters to the north, then distance[1] meters to the west, distance[2] meters to the south, distance[3] meters to the east, and so on. In other words, after each move, your direction changes counter-clockwise.

Return true if your path crosses itself or false if it does not.

 

Example 1:

Input: distance = [2,1,1,2]
Output: true
Explanation: The path crosses itself at the point (0, 1).

Example 2:

Input: distance = [1,2,3,4]
Output: false
Explanation: The path does not cross itself at any point.

Example 3:

Input: distance = [1,1,1,2,1]
Output: true
Explanation: The path crosses itself at the point (0, 0).

 

Constraints:

  • 1 <= distance.length <= 105
  • 1 <= distance[i] <= 105

Solution

We can simulate the movement of the robot and consider the possible collisions with other tracks. For example, when moving north, the robot may intersect with tracks moving west, east, or north. Similarly, when moving west, the robot may collide with tracks moving north, south, or west. We can continue this process for other directions as well.

For instance, when moving west, we can consider the conditions for collisions with tracks moving north, south, or west.

Code

class Solution {
  public:
    bool isSelfCrossing(vector<int> &distance) {
        int n = distance.size();
        if (n <= 3) {
            return 0;
        }
        for (int i = 3; i < n; ++i) {
            cout << i << endl;
            if (i == 3) {
                if (distance[2] <= distance[0] && distance[3] >= distance[1]) {
                    return true;
                }
            } else if (i == 4) {
                if ((distance[i - 1] == distance[i - 3] && distance[i] + distance[i - 4] >= distance[i - 2]) || (distance[i] >= distance[i - 2] && distance[i - 1] <= distance[i - 3])) {
                    return true;
                }
            } else {
                if ((distance[i - 1] <= distance[i - 3] && distance[i] >= distance[i - 2]) || (distance[i] + distance[i - 4] >= distance[i - 2] && distance[i - 1] + distance[i - 5] >= distance[i - 3] && distance[i - 3] > distance[i - 5] && distance[i - 2] > distance[i - 4] && distance[i - 1] <= distance[i - 3]) || (distance[i - 1] == distance[i - 3] && distance[i] + distance[i - 4] >= distance[i - 2])) {
                    return true;
                }
            }
        }
        return false;
    }
};