Как работает итератор в следующей программе - PullRequest
Новая
       29

Как работает итератор в следующей программе

0 голосов
/ 23 мая 2019

Следующая программа решает лабиринт без рекурсии.Программа работает, но я не могу понять, как работает итератор 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} `

соответственно.

simpleMaze в main() показывает связи между элементами и путем лабиринта.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

1 Ответ

1 голос
/ 23 мая 2019

В строке 19 вы распечатываете первую позицию рядом с «текущей» позицией.

В строке 21 вы распечатываете места, связанные с «текущей» позицией, которую вы считаете. Вы посещаете позицию, идущую вперед, только если вы никогда не посещали ее раньше.

Если не существует не посещенных «следующих» мест, вы знаете, что решение не предполагает прохождения «текущего» местоположения, поэтому вы возвращаетесь на один шаг назад и пробуете более поздние подключения оттуда.

Выполните несколько шагов: 

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
....
...