在迷宫中找到所有可能的路径

Question

在迷宫中找到所有可能的路径

maze

8

我正在尝试创建一个程序，它将遍历一个随机生成的迷宫，其中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);
  }
}

例如，如果我有这个迷宫：

它会给我找到的第一条路径。

虽然它需要绕路走，因为它喜欢按照向下、向上、向右和向左的顺序前进，但它仍然是一条路径。

所以，最终，我不知道如何迭代多条路径。

- r2333

我建议使用A*搜索算法。有许多易于使用的实现方法。它可以根据您指定的几个因素配置以找到最佳路径。如果您真的需要手动完成此操作，请记住可能会出现无限循环，因为可能的路径可以包括任意数量的冗余的“左右”或“左上上右下下”等方向。为了避免这种情况，我建议将“玩家”所在的方格设置为墙壁，以便玩家无法返回该方格，从而避免无限循环。 - Ultimater

你可以淹没迷宫并尝试对“可到达区域”进行排列组合（类似于旅行商问题），以创建大量可能的路径... - Martin Frank

2个回答

1

我终于为你找到了问题的解决方案。但说实话，这不是我开发的解决方案，其他人（即：Schröder）在此之前就有这个想法了！

问题由Schröder描述，但看一下德语翻译，讲述了如何对二叉树进行排列组合。

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

正如您所看到的，这些都是穿越4x4方格的解决方案（缺少镜像部分，但这是不幸的）。

- Martin Frank

请注意：如果您在前进和后退的路径上移动，最终可以创建无限数量的路径 =) 您肯定知道这一点，也肯定不是有意为之的 ^_^ - Martin Frank

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stefan Haustein · Accepted Answer

简单有效的解决方案，使用与此相似问题中的示例迷宫(该问题被标记为重复，但可以独立编译)：使用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