Найти все возможные пути через лабиринт

Question

Я пытаюсь создать программу, которая будет проходить случайно созданный лабиринт, где 1 открыты, а 0 - стены. начиная с верхнего левого угла и заканчивая в правом нижнем углу. Путь может идти вверх, вниз, влево и вправо.

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

Я читал несколько разных версий этой проблемы, но я не могу найти ее вполне с моими параметрами.

Вот мой код, я опустил часть, где я произвольно создаю свой лабиринт.

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

} 

Я пропустил часть своей основной, где я случайно генерирую свой лабиринт.

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

Например, если у меня есть лабиринте

1100111111 
1101111111 
1111110110 
1110011111 
1101101011 
1111101011 
1110111101 
1100111111 
1110111011 
1101101111 

Это дает мне первый путь, который он находит

1000000000 
1001100000 
1111110000 
1100011000 
1100001000 
1100001000 
1100001000 
1100001011 
1100001011 
1100001111 

Хотя это занимает окольным путем попасть туда, в связи с предпочтения идти в порядке вниз, вверх, вправо и влево, это еще один путь.

Так что, в конечном счете, я не уверен, как итерации для нескольких путей.

Answer 1

Я, наконец, нашел решение на ваш вопрос. но, честно говоря, это не решение, которое я разработал, некоторые другие люди (а именно: Schröder) имели эту идею раньше!

проблема описана Schröder, но посмотрите на german translation, говоря о перестановке двоичного дерева.

преобразуйте свой путь и все доступные узлы в двоичное дерево и переставьте его! (Но имейте в виду, что может быть много много решений)

, как вы можете увидеть все эти решения для пересечения 4x4 квадрат (отсутствующий зеркальную часть, но тот, увы).

Answer 2

Непосредственные полностью рабочий раствор, используя пример лабиринт из этого подобного вопроса (который был отмечен как дубликат, но был автономным компилируется): Find all paths in a maze using DFS

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

#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 версия: https://code.sololearn.com/cYn18c5p7609