找到穿过迷宫的所有可能路径 [英] Find all possible paths through a maze
问题描述
我正在尝试创建一个程序，该程序将遍历随机生成的迷宫，其中1是打开的，0是墙壁.从左上角开始，到右下角结束.路径可以向上，向下，向左和向右.
I'm trying to create a program that will traverse a randomly generated maze where 1's are open and 0's are walls. starting in the top left and ending in the bottom right. The path can go up, down, left, and right.
当前，我的程序为我提供了一种解决方案，但我无法使其打印多个路径.
Currently, my program gives me a solution, but I'm having trouble getting it to print more than one path.
我已经读过这个问题的几种不同版本，但是我无法用我的参数找到一个版本.
I've read several different versions of this problem, but I'm unable to find one quite with my parameters.
这是我的代码，我省略了随机生成迷宫的部分.
Here's my code, I omitted the part where I randomly generate my maze.
#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;
}
我省略了主体的随机生成迷宫的部分.
I've omitted the part of my main where I randomly generate my maze.
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
它给了我找到的第一条路
It gives me the first path that it finds
1000000000
1001100000
1111110000
1100011000
1100001000
1100001000
1100001000
1100001011
1100001011
1100001111
虽然到达目的地需要花一些时间，但由于偏爱按上下，上，右和左的顺序走，所以它仍然是一条路.
Though it takes a roundabout way of getting there, due to the preferences of going in order of down, up, right, and left, it is still one path.
所以最终，我不确定如何迭代多个路径.
So ultimately, I'm not sure how to iterate for multiple paths.
推荐答案
使用来自类似问题的示例迷宫(标记为重复但可独立编译)直接使用完整的解决方案:
Straightforward fully working solution using the example maze from this similar question (which was marked as duplicate but was standalone compilable): Find all paths in a maze using DFS
它使用具有直接递归的简单DFS，这似乎与此处的问题相同.它在单个字符串实例中跟踪当前轨道，并修改迷宫以阻止当前轨道.
It uses a simple DFS with straightforward recursion, which seems the same approach as in the question here. It keeps track of the current track in a single string instance and modifies the maze in place to block off the current track.
#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
这篇关于找到穿过迷宫的所有可能路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
