乌龟穿越自己的路径谜题/算法

Question

在下面寻求解决此问题的帮助。我已经通过存储每个移动的所有坐标来解决它，但是我认为这不符合时间和 space 复杂性要求。

还提到可以修改输入数组。
这几乎感觉像是一个提示或可能解决方案的一部分。

免责声明...这不是家庭作业，我不会试图将任何解决方案当作我自己的解决方案。我只是好奇，也很生气:)

我正在使用 C#

A non-empty zero-indexed array A of N positive integers is given. A LOGO turtle stands at (0,0) heading North. It moves A[0] steps forward and turns by 90 degrees clockwise. Then it moves A[1] steps forward and turns clockwise by 90 degrees. And so on.

For example, given: A[0] = 1 A[1] = 3 A[2] = 2 A[3] = 5 A[4] = 4 A[5] = 4 A[6] = 6 A[7] = 3 A[8] = 2

The turtle walks as follows: (0, 0) -> (0, 1) 1st move, 1 step North (0, 1) -> (3, 1) 2nd move, 3 steps East (3, 1) -> (3, -1) 3rd move, 2 steps South (3, -1) -> (-2, -1) 4th move, 5 steps West (-2, -1) -> (-2, 3) 5th move, 4 steps North (-2, 3) -> (2, 3) 6th move, 4 steps East (2, 3) -> (2, -3) 7th move, 6 steps South (2, -3) -> (-1, -3) 8th move, 3 steps West (-1, -3) -> (-1, -1) 9th move, 2 steps North

In the 7th and 9th moves the turtle touches its previous path, namely: at point (2, 1) in the 7th move at point (2, -1) in the 7th move at point (-1, -11) in the 9th move

Write a function: class Solution { int solution(int[] A); } that, given a description of the turtle’s walk in array A, returns the number of the first move in which the turtle touches its previous path, or 0 if no such situation occurs. For example, given array A as defined above, the function should return 7, because the turtle touches its previous path at point (2, 1) in the 7th move.

Assume that: N is an integer within the range [1..100,000]; each element of array A is an integer within the range

Complexity: expected worst-case time complexity is O(N); expected worst-case space complexity is O(1), beyond input storage (not counting the storagerequired for input arguments).

Elements of input arrays can be modified.

public static int Run(int[] input)
{
    for (int i = 3; i < input.Length; i++)
    {
        if (input[i - 1] <= input[i - 3]) //If touching previous path is possible on this move
        {
            if (input[i] >= input[i - 2]) //this move >= opposite side
                return i + 1;

            if (1 == 0) //At least 1 other case here, but i'm stumped
                return i + 1;
        }
    }
    return 0;

}

Answer 1

我不知道这是否是最佳解决方案，但我认为您需要从当前索引返回 4 或 5 以检查这些路径是否可以交叉：

public static int Run(int[] input)
{
    for (int i = 3; i < input.Length; i++)
    {
        if (input[i-1] <= input[i-3]) //If touching previous path is possible on this move
        {
            if (input[i] >= input[i-2]) //this move >= opposite side
                return i + 1;

            int fourBack = i >= 4 ? input[i-4] : 0; // Handle case where i < 4
            int fiveBack = i >= 5 ? input[i-5] : 0; // Handle case where i < 5

            if (input[i-1] >= input[i-3] - fiveBack 
             && input[i]   >= input[i-2] - fourBack 
             && input[i-2] >= fourBack)
                return i + 1;
        }
    }

    return 0;
}

乌龟穿越自己的路径谜题/算法

Turtle crossing its own path puzzle / algorithm

c#

algorithm

puzzle