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

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

Простое, полностью рабочее решение, использующее пример лабиринта из этого похожего вопроса (который был помечен как дубликат, но был автономно скомпилирован): найти все пути в лабиринте с использованием 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;
}

Запускаемая версия: https://code.sololearn.com/cYn18c5p7609

Answer 2

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

проблема описана Шредером, но посмотрите на перевод на немецкий язык, говорящий о перестановке бинарного дерева.

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

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