Finde alle möglichen Wege durch ein Labyrinth

Question

Ich versuche ein Programm zu erstellen, das ein zufällig erzeugtes Labyrinth durchquert, in dem 1s offen und 0s Wände sind. beginnend in der oberen linken und endet in der unteren rechten Ecke. Der Pfad kann nach oben, unten, links und rechts gehen.

Momentan gibt mir mein Programm eine Lösung, aber ich habe Probleme damit, mehr als einen Pfad zu drucken.

Ich habe mehrere verschiedene Versionen dieses Problems gelesen, aber ich kann mit meinen Parametern keine finden.

Hier ist mein Code, ich habe den Teil weggelassen, wo ich zufällig mein Labyrinth erzeuge.

Ich habe den Teil meiner Haupt weggelassen, wo ich zufällig mein Labyrinth generieren.

int main(){ 

if(!solveMaze(**mat, 0, 0, sol, 0)){ 
    printf("No possible paths, run program again\n"); 
    } 
    else{ 
    printf("the shortest path is %d\n", minMatrix); 
    } 
} 

Zum Beispiel, wenn ich das Labyrinth haben

1100111111 
1101111111 
1111110110 
1110011111 
1101101011 
1111101011 
1110111101 
1100111111 
1110111011 
1101101111 

Es gibt mir den ersten Weg, dass es

1000000000 
1001100000 
1111110000 
1100011000 
1100001000 
1100001000 
1100001000 
1100001011 
1100001011 
1100001111 

findet Obwohl es einen Umweg nimmt, dorthin zu gelangen, aufgrund der Vorlieben gehen in der Reihenfolge von unten, oben, rechts und links, es ist immer noch ein Weg.

Also letztlich bin ich nicht sicher, wie für mehrere Pfade zu iterieren.

Answer 1

Ich habe endlich die Lösung für Ihre Frage gefunden. Aber ehrlich gesagt ist es keine Lösung, die ich entwickelt habe, einige andere Leute (nämlich Schröder) hatten diese Idee schon einmal!

das Problem wird von Schröder beschrieben, aber werfen Sie einen Blick auf die german translation spricht von Permutation eines Binärbaums.

transformieren Sie Ihren Pfad und alle erreichbaren Knoten in einen Binärbaum und permutieren Sie ihn! (Aber seien Sie gewarnt, kann es viele viele Lösungen sein)

, wie Sie das alles sind Lösungen für die Überquerung ein 4x4 Quadrat sehen (das gespiegelte Teil fehlt, aber das ist leider).

Answer 2

Geradlinig voll funktionsfähige Lösung, die das Beispiel Labyrinth aus dieser ähnlichen Frage (die als Duplikat markiert wurde, war aber eigenständige übersetzbar) mit: Find all paths in a maze using DFS

Es verwendet eine einfache DFS mit einfacher Rekursion, die wie in der den gleichen Ansatz scheint Frage hier. Es verfolgt den aktuellen Track in einer einzelnen String-Instanz und modifiziert das Labyrinth, um den aktuellen Track zu blockieren.

#include <iostream> 
#include <string> 

const int WIDTH = 6; 
const int HEIGHT = 5; 

void check(int x, int y, int dest_x, int dest_y, 
      int (&maze)[HEIGHT][WIDTH], std::string& path) { 
    if (x < 0 || y < 0 || x >= WIDTH|| y >= HEIGHT || !maze[y][x]) { 
    return;   
    } 
    int len = path.size(); 
    path += (char) ('0' + x); 
    path += ','; 
    path += (char) ('0' + y); 

    if (x == dest_x && y == dest_y) { 
    std::cout << path << "\n"; 
    } else { 
    path += " > "; 
    maze[y][x] = 0; 
    check (x + 0, y - 1, dest_x, dest_y, maze, path); 
    check (x + 0, y + 1, dest_x, dest_y, maze, path); 
    check (x - 1, y + 0, dest_x, dest_y, maze, path); 
    check (x + 1, y + 0, dest_x, dest_y, maze, path); 
    maze[y][x] = 1; 
    } 

    path.resize(len); 
} 


int main() { 
    int maze[HEIGHT][WIDTH] = { 
     {1,0,1,1,1,1}, 
     {1,0,1,0,1,1}, 
     {1,1,1,0,1,1}, 
     {0,0,0,0,1,0}, 
     {1,1,1,0,1,1}}; 

    std::string path; 
    check(0, 0, 4, 3, maze, path); 
    return 0; 
} 

Runnable Version: https://code.sololearn.com/cYn18c5p7609