java: ширина первого обхода с обратным отсчетом для лабиринта

Question

Я пытаюсь реализовать первый проход шириной для лабиринта. Это код, который я до сих пор использовал связанный список, но я не уверен, что он сначала ищет ширину. Это правильный способ сделать это? любые предложения, комментарии?

public boolean traverseBreadth(){ 
    //traverse the floor from entrance to exit 
    //stepping only on red tiles 
    steps = new LinkedList<Tile>(); 
    possibleSteps = new LinkedList<Tile>(); 
    //reset markings 
    reset(); 
    //push the entrance onto the stack 
    entrance.setVisited(); 
    steps.add(entrance); 

    System.out.println("add " + entrance); 
    nextMoves(entrance); 
    //keep going as long as we have a possibility to move 
    //and we haven't reached the end yet 
    while (!possibleSteps.isEmpty()&& (!possibleSteps.getLast().equals(exit))) 
    { 
     Tile x = possibleSteps.removeLast(); 

     x.setMarked(); //walked on that square 
     steps.add(x); //walk to that square 
     System.out.println("Walked to the square " + x); 
     //now figure out where you can walk from this square 
     nextMoves(x); 
     try { 
       Thread.currentThread().sleep(1000); 
       } 
      catch (InterruptedException e) { 
       e.printStackTrace(); 
       } 





    } 
    if (possibleSteps.getLast().equals(exit)){ 
     steps.push(possibleSteps.removeLast()); 
     System.out.println("made it from entrance to exit"); 
     System.out.println(steps.toString()); 
     return true; 
    } 
    else 
    { JOptionPane.showMessageDialog(null,"sorry can't reach the exit"); 
     return false; 
    } 

} 

Answer 1

Это не первый поиск по ширине - это глубина первой.

Есть 2 места, которые, очевидно, глубина первой

• удалить с конца пограничными (possibleTiles), а не начало.
• у вас нет иерархии обхода (от родителя к ребенку), чтобы перестроить путь обхода, только один «путь» с плитками. Поэтому сначала это глубина.

Вещи изменения:

• вместо LinkedList, изменить это в словарь. Ключом словаря будет плитка, и значение будет родителем плитки. Используйте это, чтобы восстановить свой последний путь.
• Ваша функция «moveNext», вероятно, правильная. Убедитесь, что он нажимает до конца списка.
• не pop (getLast()) from PossibleSteps. Возможные шаги должны быть очереди «Первый-в-первом-Out». Извлеките первую плиту возможных шагов (это позволит изучить плитки, наиболее близкие к началу).

вещей, чтобы улучшить:

• вместо использования плитки для отслеживания исследования, использовать Set (назовите его ExploredTile), где вы положили плитки, которые вы проходимые)
• использовать очереди вместо списка ,

Некоторые C#/псевдокод (Потому что я не на IDE)

Dictionary<Tile,Tile> path = ...; 
Queue<Tile> frontier = ...; 
Set<Tile> explored = ...; 

path[start] = null; 

while(frontier.Count > 0){ 
    var tile = frontier.Dequeue(); 

    if(explored.Contains(tile)){ 
     continue; 
    } 
    explored.add(tile); 

    if (Tile == Exit){ 
     rebuildPath(Exit); 
    }else{ 
     for (Tile t in Tile.neighbours){ 
      if (!explored.Contains(t)){ 
       frontier.Enqueue(t); 
       path[t] = tile; // Set the path hierarchy 
      } 
     } 
    } 
} 

RebuildPath

LinkedList<Tile> finalPath = ...; 

Tile parent = path[exitTile]; 
finalPath.push(exitTile); 

while(parent != null){ 
    finalPath.push(parent); 
    parent = path[parent]; 
} 

finalPath.reverse(); 

Надеюсь, я получил это право ... :)