通过迷宫找到所有可能的路径

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\xc3\xb6der）以前就有过这个想法！

\n\n

该问题由Schr\xc3\xb6der描述，但请查看关于排列二叉树的德语翻译。

\n\n

将您的路径和所有可到达的节点转换为二叉树并对其进行排列！（但请注意，可能有很多解决方案）

\n\n

\n\n

正如你所看到的，这些都是穿越 4x4 正方形的解决方案（缺少镜像部分，但可惜了）。

\n