c++ - 无法找出无限循环背后的原因

我目前正在开发一个程序，该程序可以从形成轮廓的文件中读取一组坐标，然后使用泛洪填充算法将其填充。

似乎下面的代码在无限循环中运行，但我似乎无法找出原因。

帮助或建议，非常感激:-)

    /* Flood fill */
    TargetColour = 0.0;
    NewColour = 2.0;
    starting_point = 0+slice;

    //Create queue
    queue < int > MyQue;
    //Insert first point into the queue
    MyQue.push(starting_point);

    //While loop for iterating over the nodes.
    while (!MyQue.empty()){
        //Take out the front element
        Node = MyQue.front();
        MyQue.pop();
        tmpSlice[Node] = NewColour;

        //Define the Node directions
        WestNode = Node-1;
        EastNode = Node+1;
        NorthNode = Node-sizes[1];
        SouthNode = Node+sizes[2];


        //East Node
        if (slab[EastNode] == TargetColour && floor((Node-sizes[1]*sizes[2]*floor(Node/(sizes[1]*sizes[2])))/sizes[1]) == floor((EastNode-sizes[1]*sizes[2]*floor(EastNode/(sizes[1]*sizes[2])))/sizes[1])){
            MyQue.push(EastNode);
        }
        //West Node
        if (slab[WestNode] == TargetColour && floor((Node-sizes[1]*sizes[2]*floor(Node/(sizes[1]*sizes[2])))/sizes[1]) == floor((WestNode-sizes[1]*sizes[2]*floor(WestNode/(sizes[1]*sizes[2])))/sizes[1])){
            MyQue.push(WestNode);
        }
        //North Node
        if (slab[NorthNode] == TargetColour && floor(Node / (sizes[1]*sizes[2])) == floor(NorthNode / (sizes[1]*sizes[2]))){
            MyQue.push(NorthNode);
        }
        //South Node
        if (slab[SouthNode] == TargetColour && floor(Node / (sizes[1]*sizes[2])) == floor(SouthNode / (sizes[1]*sizes[2]))){
            MyQue.push(SouthNode);
        }
    }

最佳答案

我部分地确定您的算法实际上正在终止，但是只能在很长时间之后（假设队列有足够的内存）。我需要有关sizes的值的更多详细信息以完全确定。

让我们播放一个3x3的示例字段，并假设整个floor((Node-sizes[1]*sizes[2]*floor(Node/(sizes[1]*sizes[2])))/sizes[1])只是边界检查（它是什么？）。

字段（数字是职位名称）：

1 2 3
4 5 6
7 8 9

假设starting_point = 1


MyQue = {1}


访问1，在MyQue中添加2和4

MyQue = {2，4}


访问2，在MyQue中添加3和5

MyQue = {4，3，5}


访问4，将5和7添加到MyQue

MyQue = {3，5，5，7}


访问3，将6添加到MyQue

MyQue = {5，5，7，6}


访问5，将6和8添加到MyQue

MyQue = {5，7，6，6，8}


访问5，将6和8添加到MyQue

MyQue = {7，6，6，8，6，8}


访问7，将8添加到MyQue

MyQue = {6，6，8，6，6，8}


访问6，将9添加到MyQue

MyQue = {6，8，6，8，8，9}


访问6，将9添加到MyQue

MyQue = {8，6，8，8，9，9}


访问8，将9添加到MyQue

MyQue = {6，8，8，9，9，9}


访问6，将9添加到MyQue

MyQue = {8，8，9，9，9，9}


访问8，将9添加到MyQue

MyQue = {8，9，9，9，9，9}


访问8，将9添加到MyQue

MyQue = {9，9，9，9，9，9}


造访9

MyQue = {9，9，9，9，9}


造访9

MyQue = {9，9，9，9}


造访9

MyQue = {9，9，9}


造访9

MyQue = {9，9}


造访9

MyQue = {9}


造访9



我希望这可以说明该算法如何即使在较小的字段中也经常重复相同的事情-对于较大的字段，此效果将有所增加。

因此，您可以做的是确保每个节点仅排队一次。我认为评估顺序并不重要，因此可以使用queue代替set来存储工作集。这样可以确保每个号码只能同时排队一次。

您还可以组合队列和设置，以保持评估顺序。

set < int > marker;
queue < int > MyQue;

// ... replace later in code
// MyQue.push(SomeNode);
// by
if (marker.insert(SomeNode).second) {
    MyQue.push(SomeNode);
}

编辑：稍微改变了if条件。如果插入了marker.insert(SomeNode).second，则true将为SomeNode；如果已插入false，则为SomeNode。