迭代器如何在以下程序中工作

Question

下面的程序是在没有递归的情况下解决迷宫问题。程序正在运行，但我无法弄清楚迭代器 iter 是如何工作的。

有两条评论 第 19 行 和 第 21 行。我尝试打印迭代器的值，它给我

{1,0,1,0,1,0,3,4,3,4}

和

{1,0,2,1,0,2,1,3,0,4,3,5,4,3,5,7,4,8}`

分别

main()中的simpleMaze显示了元素与迷宫路径之间的联系。由于 0 连接到 (1,3)； 1 连接到 (0,2) 等等。

迭代器用于遍历那么为什么这个程序给出这样的序列我也无法理解函数的流程solveMaze。

#include <bits/stdc++.h>

using namespace std;

list<int> solveMaze(list<int> maze[],int start,int finish) {
    unordered_set<int> visited;
    list<int> path;

    path.push_back(start);
    int currentPoint=start;
    visited.insert(currentPoint);

    while(path.back()!= finish && path.empty() == false)     {
        list<int>::iterator iter = maze[currentPoint].begin();
        bool foundOutlet = false;
        cout<<*iter<<"\n";     //line 19
        while(iter!=maze[currentPoint].end() && (foundOutlet== false)) {
        cout<<*iter<<"\n";   //line 21
            if(visited.count(*iter)==0) {
                foundOutlet = true;
            }
            else {
                iter++;
            }
        }
        if(foundOutlet)
        {
            path.push_back(*iter);
            visited.insert(*iter);
        }
        else
        path.pop_back();
        currentPoint= path.back();
    }

    return path;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    list <int> simpleMaze[9],path;
    simpleMaze[0].push_back(1);
    simpleMaze[0].push_back(3);

    simpleMaze[1].push_back(0);
    simpleMaze[1].push_back(2);

    simpleMaze[2].push_back(1);

    simpleMaze[3].push_back(0);
    simpleMaze[3].push_back(4);
    simpleMaze[3].push_back(6);


    simpleMaze[4].push_back(3);
    simpleMaze[4].push_back(5);
    simpleMaze[4].push_back(7);

    simpleMaze[5].push_back(4);

    simpleMaze[6].push_back(3);

    simpleMaze[7].push_back(4);
    simpleMaze[7].push_back(8);

    simpleMaze[8].push_back(7);


    path = solveMaze(simpleMaze,0,8);

    list<int>::iterator it;
    for(it=path.begin();it!=path.end();++it)
    {
        cout<<*it<<"\n";
    }
    return 0;

}

迷宫的解是

0 3 4 7 8

Answer 1

在第 19 行，您打印出与 "current" 位置相邻的第一个位置。

在第 21 行，您打印出与您考虑的 "current" 位置相关的位置。如果您以前从未访问过，那么您只会访问未来的位置。

如果没有未访问的 "next" 地方，您知道解决方案不涉及通过 "current" 位置，因此您返回一步，然后从那里尝试稍后的连接。

通过几个步骤进行跟踪：

Start 
 At 0
  See 1, it is unvisited, go there
 At 1
  See 0, it is visited
  See 2, it is unvisited, go there
 At 2
  See 1, it is visited
  No more locations at 2, backtrack
 At 1
  See 0, it is visited
  See 2, it is visited
  No more locations at 1, backtrack
 At 0
  See 1, it is visited
  See 3, it is unvisited, go there
....

迭代器如何在以下程序中工作

How does the iterator works in following program

c++

stl

maze

list

backtracking