我需要找到从给定点开始和结束的循环。不能保证它是否存在。
我使用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;
}
但是它不起作用。找到的路径包含两个点:起点和它的第一个邻居。
我做错了什么?
编辑: 忘了提一下...水平连接之后必须是垂直、水平、垂直等等... 而且每行和每列中最多只能有两个点(两个或没有)在循环中。但这个条件与“循环必须是最短的”是相同的。