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

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

举例来说，如果我有迷宫

它让我找到

，尽管它到达那里的一种迂回的方式，由于第一路径按照向下，向上，向右和向左的顺序进行偏好，它仍然是一条路径。

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

来源

2016-05-11 r2333

我建议使用[A *]（https://en.wikipedia.org/wiki/A*_search_algorithm）。那里有许多易于使用的实现。它可以配置为根据您可以指定的几个因素找到最佳路径。如果你真的需要手动做这件事，那么需要记住的一件事是可能的无限循环，因为可能的路径可以包括任意数量的冗余背靠背“左右”或“左上 - 右下 - 下”方向。为了避免这种情况，我建议将“玩家”放在墙上的方格放在墙上，这样玩家就不能移回去，避免无限循环。 – Ultimater

你可以淹没迷宫，并尝试排列'可到达的领域'（la travelingsalesman问题），以创建大量的可能路径...... –

我终于找到你解决你的问题。但老实说，这不是我开发的解决方案，其他人（即：施罗德）之前也有过这个想法！

该问题描述为Schröder，但看看german translation说到排列二叉树。

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

，你可以看到这些都是穿越一个4x4正方形的所有解决方案（缺少镜像的一部分，但多数民众赞成唉）。

使用此类似的问题的例子迷宫（其中被标记为重复但独立编译）

来源

2016-05-27 09:02:09

注意：如果你前进和后退的路径上移动，你最终可以创建一个无限量的路径=）你当然知道这一点，当然不打算这样做^ _ ^ –

直白完全工作的解决方案：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

来源

2017-10-19 10:51:28

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

回答

相关问题