Trova tutti i possibili percorsi attraverso un labirinto

Question

Sto provando a creare un programma che attraverserà un labirinto generato casualmente dove 1 sono aperti e 0 sono muri. iniziando in alto a sinistra e finendo in basso a destra. Il percorso può salire, scendere, a sinistra e a destra.

Attualmente, il mio programma mi fornisce una soluzione, ma ho difficoltà a farlo stampare più di un percorso.

Ho letto diverse versioni di questo problema, ma non riesco a trovarne uno con i miei parametri.

Ecco il mio codice, ho omesso la parte in cui generi a caso il mio labirinto.

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <stdbool.h> 

int n, minMatrix, solIndex = 1, minLen = 10000000; //I use the latter 3 variables in order to find the shortest path, not relevant for now 


bool solveMaze(int mat[n][n],int x, int y, int sol[][n], int count){ 

int i, j; 
    if((!(x >= 0 && x <n && y >=0 && y < n)) || mat[x][y] == 0 || sol[x][y] == 1){ 
    return false; 
    } 

    if(x == n-1 && y == n-1){ 
    sol[x][y] = 1; 

    printf("Solution %d is:\n", solIndex); 
    for(i = 0; i < n; i++) 
    { 
     for(j=0;j<n;j++) 
     { 
     printf("%d", sol[i][j]); 
     } 
     printf("\n"); 
    } 

    if(count<minLen) 
    { 
     minLen = count; 
     minMatrix = solIndex; 
    } 
    solIndex +=1; 
    sol[x][y] = 0; 
    return true; 
    } 

    sol[x][y] = 1; 

    if(solveMaze(mat, x+1, y, sol, count+1)){ 
    return true; 
    } 

    if(solveMaze(mat, x-1, y, sol, count+1)){ 
    return true; 
    } 

    if(solveMaze(mat, x, y+1, sol, count+1)){ 
    return true; 
    } 

    if(solveMaze(mat, x, y-1, sol, count+1)){ 
    return true; 
    } 
    sol[x][y] = 0; 
    return false; 

} 

Ho omesso la parte del mio main in cui ho generato a caso il mio labirinto.

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); 
    } 
} 

Per esempio se ho il labirinto

1100111111 
1101111111 
1111110110 
1110011111 
1101101011 
1111101011 
1110111101 
1100111111 
1110111011 
1101101111 

Mi dà il primo percorso che trova

1000000000 
1001100000 
1111110000 
1100011000 
1100001000 
1100001000 
1100001000 
1100001011 
1100001011 
1100001111 

Anche se ci vuole un modo indiretto di arrivarci, a causa della preferenze di andare in ordine di down, up, right e left, è ancora un percorso.

Quindi, in definitiva, non sono sicuro su come iterare per più percorsi.

Answer 1

ho finalmente trovato la soluzione alla tua domanda. ma onestamente non è una soluzione che ho sviluppato, altre persone (vale a dire Schröder) hanno avuto questa idea prima!

il problema è descritto da Schröder, ma dare un'occhiata al german translation parlando di permutando un albero binario.

trasforma il tuo percorso e tutti i nodi raggiungibili in un albero binario e permutalo! (Ma attenzione, ci possono essere molti molte soluzioni)

come si può vedere questi sono tutte le soluzioni per attraversare un quadrato 4x4 (manca la parte specchiata, ma questo purtroppo).

Answer 2

soluzione completamente funzionante Semplice usando l'esempio labirinto a questa domanda simile (che è stato contrassegnato come duplicato ma era compilabile standalone): Find all paths in a maze using DFS

Si utilizza un semplice DFS con ricorsione semplice, che sembra lo stesso approccio nel domanda qui. Tiene traccia della traccia corrente in una singola istanza di stringa e modifica il labirinto in atto per bloccare la traccia corrente.

#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; 
} 

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