maze - 找到穿过迷宫的所有可能路径

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

使用来自此类似问题的示例迷宫(被标记为重复但可以独立编译)的直接完全工作解决方案: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;
}

可运行版本:https://code.sololearn.com/cYn18c5p7609