循环查找算法

Question

我需要找到一个在给定点开始和结束的循环.不保证它存在.我bool[,] points用来指示哪个点可以循环.点数只能在网格上.points指示网格上的给定点是否可以循环.我需要使用最小点数来找到这个循环.一点只能使用一次.连接只能是垂直或水平.

让这成为我们的观点(红色是起点):

删除死的ImageShack链接

我意识到我可以这样做:

while(numberOfPointsChanged)
{
    //remove points that are alone in row or column
}

所以我有:

删除死的ImageShack链接

现在,我可以找到路径.

删除死的ImageShack链接

但是如果有一些点没有被这个循环删除但不应该在路径中呢？

我写了代码:

class MyPoint
{
    public int X { get; set; }
    public int Y { get; set; }
    public List<MyPoint> Neighbours = new List<MyPoint>();
    public MyPoint parent = null;
    public bool marked = false;
}

    private static MyPoint LoopSearch2(bool[,] mask, int supIndexStart, int recIndexStart)
    {
        List<MyPoint> points = new List<MyPoint>();

        //here begins translation bool[,] to list of points
        points.Add(new MyPoint { X = recIndexStart, Y = supIndexStart });

        for (int i = 0; i < mask.GetLength(0); i++)
        {
            for (int j = 0; j < mask.GetLength(1); j++)
            {
                if (mask[i, j])
                {
                    points.Add(new MyPoint { X = j, Y = i });
                }
            }
        }

        for (int i = 0; i < points.Count; i++)
        {
            for (int j = 0; j < points.Count; j++)
            {
                if (i != j)
                {
                    if (points[i].X == points[j].X || points[i].Y == points[j].Y)
                    {
                        points[i].Neighbours.Add(points[j]);
                    }
                }
            }
        }
        //end of translating

        List<MyPoint> queue = new List<MyPoint>();
        MyPoint start = (points[0]); //beginning point
        start.marked = true; //it is marked
        MyPoint last=null;   //last point. this will be returned
        queue.Add(points[0]);


        while(queue.Count>0)
        {
            MyPoint current = queue.First(); //taking point from queue
            queue.Remove(current);           //removing it

            foreach(MyPoint neighbour in current.Neighbours) //checking Neighbours
            {
                if (!neighbour.marked) //in neighbour isn't marked adding it to queue
                {
                    neighbour.marked = true;
                    neighbour.parent = current;
                    queue.Add(neighbour);
                }
                //if neighbour is marked checking if it is startig point and if neighbour's parent is current point. if it is not that means that loop already got here so we start searching parents to got to starting point
                else if(!neighbour.Equals(start) && !neighbour.parent.Equals(current))
                {                        
                    current = neighbour;
                    while(true)
                    {
                        if (current.parent.Equals(start))
                        {
                            last = current;
                            break;
                        }
                        else
                            current = current.parent;

                    }
                    break;
                }
            }
        }

        return last;            
    }

但它不起作用.它找到的路径包含两点:start和它的第一个邻居.
我究竟做错了什么？

编辑: 忘了提...水平连接后必须有垂直,水平,垂直等等...每行和每列中的更多内容需要最多两个点(两个或没有)周期.但这种情况与"循环必须是最短的"相同.

Answer 1

这就是我所做的。我不知道它是否已优化，但它确实可以正常工作。我还没有按照@marcog 的建议对这些点进行排序。

private static bool LoopSearch2(bool[,] mask, int supIndexStart, int recIndexStart, out List<MyPoint> path)
    {
        List<MyPoint> points = new List<MyPoint>();
        points.Add(new MyPoint { X = recIndexStart, Y = supIndexStart });

        for (int i = 0; i < mask.GetLength(0); i++)
        {
            for (int j = 0; j < mask.GetLength(1); j++)
            {
                if (mask[i, j])
                {
                    points.Add(new MyPoint { X = j, Y = i });
                }
            }
        }

        for (int i = 0; i < points.Count; i++)
        {
            for (int j = 0; j < points.Count; j++)
            {
                if (i != j)
                {
                    if (points[i].X == points[j].X || points[i].Y == points[j].Y)
                    {
                        points[i].Neighbours.Add(points[j]);
                    }
                }
            }
        }

        List<MyPoint> queue = new List<MyPoint>();
        MyPoint start = (points[0]);
        start.marked = true;
        queue.Add(points[0]);

        path = new List<MyPoint>();

        bool found = false;

        while(queue.Count>0)
        {
            MyPoint current = queue.First();
            queue.Remove(current);

            foreach (MyPoint neighbour in current.Neighbours)
            {
                if (!neighbour.marked)
                {
                    neighbour.marked = true;
                    neighbour.parent = current;
                    queue.Add(neighbour);
                }
                else
                {
                    if (neighbour.parent != null && neighbour.parent.Equals(current))
                        continue;

                    if (current.parent == null)
                        continue;

                    bool previousConnectionHorizontal = current.parent.Y == current.Y;
                    bool currentConnectionHorizontal = current.Y == neighbour.Y;

                    if (previousConnectionHorizontal != currentConnectionHorizontal)
                    {
                        MyPoint prev = current;

                        while (true)
                        {
                            path.Add(prev);
                            if (prev.Equals(start))
                                break;
                            prev = prev.parent;
                        }

                        path.Reverse();

                        prev = neighbour;

                        while (true)
                        {
                            if (prev.Equals(start))
                                break;
                            path.Add(prev);                                
                            prev = prev.parent;
                        }

                        found = true;
                        break;
                    }                      
                }
                if (found) break;
            }
            if (found) break;
        }

        if (path.Count == 0)
        {
            path = null;
            return false;
        }
        return true;   
    }