Estou tentando criar um programa que irá atravessar um labirinto gerado aleatoriamente onde 1's estão abertos e 0's são paredes. começando no canto superior esquerdo e terminando no canto inferior direito. O caminho pode subir, descer, esquerda e direita.

Atualmente, meu programa fornece uma solução, mas estou tendo problemas para imprimir mais de um caminho.

Eu li várias versões diferentes desse problema, mas não consigo encontrar uma com meus parâmetros.

Aqui está o meu código, eu omiti a parte em que gero aleatoriamente meu 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;

}

Omiti a parte do meu main onde gero meu labirinto aleatoriamente.

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

Por exemplo, se eu tiver o labirinto

1100111111
1101111111
1111110110
1110011111
1101101011
1111101011
1110111101
1100111111
1110111011
1101101111

Me dá o primeiro caminho que encontra

1000000000
1001100000
1111110000
1100011000
1100001000
1100001000
1100001000
1100001011
1100001011
1100001111

Embora seja uma maneira indireta de chegar lá, devido às preferências de ir em ordem de descer, subir, direita e esquerda, ainda é um caminho.

Então, finalmente, não sei como iterar para vários caminhos.