检查N个部分是否相交

Question

伙计们！我需要实现 static bool CheckSectionsIntersect 函数来检查截面是否相交（右→；左←；下↓；向上↑)。以一系列方向的形式给定一个包含固定维度的 N 个连续垂直和水平部分的列表。我不得不认为我会有 N 部分的路线。如果我到达以前去过的地方，该功能应该 return True 。例如：

N = 6: { 上、左、下、下、右、上} - return 正确。

⬇⬅
⬇⬆  <- Start
➡⬆

N = 4：{下、左、上、左} - return 错误。

⬅⬇  <- Start
⬆⬅

我写的代码，但不完整，因为我需要一些关于函数应该如何的建议：

    static void Main()
    {
        string userInput = Console.ReadLine();
        int numberOfSections = Convert.ToInt32(userInput);
        string[] sectionDirection = new string[numberOfSections];
        for (int i = 0; i < numberOfSections; i++)
        {
            sectionDirections[i] = Console.ReadLine();
        }

        Console.WriteLine(CheckSectionsIntersect(sectionDirection, numberOfSections));
    }

    static bool CheckSectionsIntersect(string[] sectionDirection, int numberOfSections)
    {
        return true; // I need an implementation here
    }
}

}

请问我对这个实现有什么建议吗？非常感谢！

Answer 1

如果您想到笛卡尔网格，并且从 0,0 开始，x 坐标为 left/right incrementing/decrementing，y 坐标为 up/down，那么答案是你会随时回到 0,0 点吗？

static Dictionary<string,(int X,int Y)> transforms = new Dictionary<string, (int X, int Y)>{
    ["U"] = (0,1),
    ["D"] = (0,-1),
    ["L"] = (-1,0),
    ["R"] = (1,0)
};

static bool CheckSectionsIntersect(string[] sectionDirection, int numberOfSections)
{
    (int X, int Y) pos = (0,0);
    for(var i = 0;i<numberOfSections;i++)
    {
        if(!transforms.TryGetValue(sectionDirection[i], out var transform))
           throw new ArgumentException("sectionDirections");
        pos.X += transform.X;
        pos.Y += transform.Y;
        if(pos.X == 0 && pos.Y == 0)
            return true;                
    }
    return false;
}

你的 2 个测试用例的实例：https://dotnetfiddle.net/p5JY61

以上仅检查您最终回到 0,0 - 但是，如果您想确定您是否输入了任何 co-ordine 您之前去过的地方，您只需要跟踪您去过的地方一直在使用一个集合，而不是检查你是否回到 0,0 检查你是否在你以前去过的任何地方。

static bool CheckSectionsIntersect(string[] sectionDirection, int numberOfSections)
{
    (int X, int Y) pos = (0,0);
    var visited = new List<(int X, int Y)>{ pos };
    for(var i = 0;i<numberOfSections;i++)
    {
        if(!transforms.TryGetValue(sectionDirection[i], out var transform))
           throw new ArgumentException("sectionDirections");
        (int X, int Y) newPos = (pos.X + transform.X, pos.Y + transform.Y);
        
        if(visited.Contains(newPos))
            return true;    
                    
        pos = newPos;
        visited.Add(newPos);
    }
    return false;
}

实例：https://dotnetfiddle.net/FyJYrr

Answer 2

我不确定我明白你在说什么。如果你想看看你是否在你去过的地方结束，只需制作一个元组数组即可。在每次移动中保存您的坐标（从 0,0 开始）。在路径的末尾检查您的坐标是否在数组中。或者在每次移动结束时，如果您想检查您已经去过的地方。

编辑：

static bool CheckSectionsIntersect(string[] sectionDirection, int numberOfSections)
    {
        (int X, int Y) pos = (0, 0); //Variable to track our actual position. Start position (0,0)
        List<(int X, int Y)> coordinates = new List<(int X, int Y)>(); //List where we are going to keep the coordinates
        foreach (string move in sectionDirection) //for each move
        {
            coordinates.Add(pos); //Add our current position to the list
            switch (move)         //Make a move
            {
                case "left":
                    pos.X -= 1;
                    break;
                case "right":
                    pos.X += 1;
                    break;
                case "down":
                    pos.Y -= 1;
                    break;
                case "up":
                    pos.Y += 1;
                    break;
            }
            if (coordinates.Contains(pos)) { return true; } //If our new position is already in the list, we have been there.
        }
        return false;
    }

我已经测试过它并且有效。为此，使用列表比使用数组更容易。这是由于方法 .Add() 和 .contains().

此代码不是最强的（例如，它不接受大写字母）。但既然你是初学者，那应该就足够了。我鼓励您改进它以继续学习。

检查N个部分是否相交

Check if N sections intersect

c#

intersection

function

directions