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;
}
};
标签:distance,north,335,west,Self,moving,&&,Crossing,true
From: https://www.cnblogs.com/zwyyy456/p/17588154.html