迷宫问题全部路径和最短路径求解

程序员的救赎

下面的代码能找出一条路径，不知道怎么修改才能求出全部路径。

以下是输入的迷宫：
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 0 1 1 1 1
1 1 0 1 0 1 1 1 1 1
1 0 1 0 0 0 0 0 1 1
1 0 1 1 1 0 1 1 1 1
1 1 0 0 1 1 0 0 0 1
1 0 1 1 0 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1

#include <iostream>
#include<stack>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
const int XLEN=8,YLEN=10;//默认迷宫行数和列数
int m,p;// 出口坐标
int maze[XLEN][YLEN];//迷宫数组
int mark[XLEN][YLEN];//访问标记数组
struct Offsets{
        int a,b;//a和b是x y方向的偏移 
}; 
Offsets directions[8]={
        {-1,0},//上
        {-1,1},//右上
        {0,1},//右
        {1,1},//右下
        {1,0},//下
        {1,-1},//左下
        {0,-1},//左
        {-1,-1},//左上 
};
struct items{
        int x,y,dir;//栈结点定义 
}; 

void outputpath(stack<items> a, items Tmp) {
    stack<items> b; 
    b.push(Tmp);
    while(!a.empty()){
                                        b.push(a.top());
                                        a.pop(); 
                                } 
                                while(!b.empty()){ 
                                        cout<<"<"<<b.top().x<<","<<b.top().y<<">"<<" ";
                                        b.pop();
                                    
                                } 
}
void Path(int x,int y,int m,int n){//x,y为入口坐标，m,n为出口坐标
        int i,j,g,h,d = 0; // i，j为当前位置， g,h为下一步的位置，d为下一步的方向 
        stack<items> S;//设置工作栈
        stack<items> St;//输出栈 
        items tmp;
        items Tmp; 
        mark[x][y]=1;//x,y是入口
        tmp.x=x,tmp.y=y;
        tmp.dir=0;
        S.push(tmp);//入口坐标入栈
        while(!S.empty()){//当栈不空，一直走下去
                tmp=S.top();//取栈顶元素
                S.pop();
                i=tmp.x;
                j=tmp.y;//取当前位置的坐标
                d=tmp.dir;
                while(d<8){
                        //找下一位置(g,h)
                        g=i+directions[d].a;
                        h=j+directions[d].b;
                        if(g==m && h==n){//到达出口 
                                //逆向存入输出栈 
                                Tmp.x=m,Tmp.y=n;
                                outputpath(S, Tmp); 
                                mark[g][h]=1;//标记已被访问
                                return;
                        }
                
                        //未到达出口
                        if(maze[g][h]==0 && mark[g][h]==0){//如果可通且未被访问
                                mark[g][h]=1;//标记已被访问
                                tmp.x=i;
                                tmp.y=j;
                                tmp.dir=d;//记录已走过的位置和前进的方向
                                S.push(tmp);
                                i=g;
                                j=h;
                                d=0;}//移到(g,h)在各个方向试探 
                        else//试探下一个方向
                                d++; 
                } 
        } 
}
int main(int argc, char** argv) {
        int i,j,x,y,m,n;
        cout<<"迷宫如下图所示："<<endl;
        for(i=0;i<XLEN;i++){
                 for(j=0;j<YLEN;j++){
                         cin>>maze[i][j];
                         mark[i][j]=0;
                 }
   }
                
        cout<<"迷宫所有路径如下："<<endl;
        Path(1,1,XLEN-2,YLEN-2);
//        cout<<"最短路径如下："<<endl;
//        cout<<"长度为："<<
//        cout<<"通路为："<<
        return 0;
}

程序员的救赎

主要是最近在用Python， 大一的数据结构都忘得差不多了。

迷雾少年

dfs可以很简单实现

迷雾少年

#include <iostream>
using namespace std;
//0 为可以移动 1为障碍
int map[][10] = 
{
1,1,1,1,1,1,1,1,1,1,
1,0,1,1,1,0,1,1,1,1,
1,0,0,0,0,1,1,1,1,1,
1,0,1,0,0,0,0,0,1,1,
1,1,1,1,1,0,1,1,1,1,
1,0,0,0,0,0,0,0,0,1,
1,0,1,1,0,0,1,1,0,1,
1,0,0,0,0,0,0,0,0,1 };
struct point
{
        int x, y;
};
point steps[100] = { 0 };
int startx = 1, starty = 1;
int endx = 5, endy = 3;
int direct[][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int row = 8, col = 10;//8行10列地图

void dfs(int deep, int x, int y)
{
        int i;
        if (x<0 || x>row - 1 || y<0 || y>col - 1 || map[x][y] == 1)
                return;
        point tmp = { x,y };
        steps[deep] = tmp;
        if (x == endx && y == endy) {//终点
                for (i = 0; i < deep+1; i++) {
                        printf("(%d,%d)-", steps[i].x, steps[i].y);
                }
                printf("\n");
                return;
        }
        for (i = 0; i < 4; i++)
        {
                map[x][y] = 1;
                dfs(deep + 1, x + direct[i][0],y+direct[i][1]);
                map[x][y] = 0;
        }
}

int main()
{
        point t = { startx,starty };
        dfs(0, startx, starty);
        return 0;
}

(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(6,4)-(6,5)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(6,5)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(6,5)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(6,4)-(6,5)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(6,5)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(6,5)-(6,4)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(3,5)-(4,5)-(5,5)-(5,6)-(5,7)-(5,8)-(6,8)-(7,8)-(7,7)-(7,6)-(7,5)-(7,4)-(7,3)-(7,2)-(7,1)-(6,1)-(5,1)-(5,2)-(5,3)-

程序员的救赎

迷雾少年 发表于 2019-5-28 00:24
(1,1)-(2,1)-(2,2)-(2,3)-(3,3)-(3,4)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(7,4)-(6,4)-(5,4)-(5,3)-
(1 ...

···你这个是四个方向的，我的是八个方向的，而且我想要的是在我基础上上面修改一下

迷雾少年

程序员的救赎 发表于 2019-5-28 09:41
···你这个是四个方向的，我的是八个方向的，而且我想要的是在我基础上上面修改一下

八个方向x-1,y-1,x+1,y+1,x-1,y+1,x-1,y+1就可以了

迷雾少年

程序员的救赎 发表于 2019-5-28 09:41
···你这个是四个方向的，我的是八个方向的，而且我想要的是在我基础上上面修改一下

dfs递归用的就是栈啊，原理一样