欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

回溯法——迷宫问题

程序员文章站 2022-05-27 08:32:01
...

回溯法——迷宫问题

1.首先我们需要自定义一个迷宫;
左上角为入口,右下角为出口,0为路,-1为墙
用二维数组存储
回溯法——迷宫问题
2.我们在走迷宫之前,首先要确立一个走的顺序,即贪心准则,我们首先试探的方向应该是下,然后是右,上,左;
为了确保每一个格子都有上下左右,我们需要给我们的迷宫加上一圈墙8*8,变成10*10;
3.当我们在一个格子上时,通过遍历格子的4个方向,来确定能否行走,若能走,走,不能走,回。

代码如下:

#include<iostream>
using namespace std;
int H[10][10];//定义一个迷宫 
int move[4][2]={1,0,0,1,-1,0,0,-1};//定义4个方向 
int Url[50][2]={0};//定义一个二位数组来存放我的路径 
int top=-1;//栈顶指针 
int cnt=0;//累计看有多少组解 
void PrintM(){
    cout<<"第"<<++cnt<<"组解"<<endl;
    for(int i=0;i<=top;i++){
        cout<<"("<<Url[i][0]<<","<<Url[i][1]<<")"<<endl;
    }
     cout<<endl;
}
void Maze(int x,int y){
    int a;int b,i;
    for(i=0;i<4;i++){//遍历4个方向 
        a=x+move[i][0];//计算下个格子的坐标 
        b=y+move[i][1];
        if(!H[a][b]){//如果下个格子可以走 
            H[a][b]=1;//将走过的路标记为1 
            top++;//将该格子的地址存入路径数组中 
            Url[top][0]=a;
            Url[top][1]=b;
            if(a==8&&b==8) PrintM();//当走到从出口时,将路径输出 
            else Maze(a,b);//否则就通过调用走到下一个格子 
            H[a][b]=0;//调用回来不论是前方格子不能走,还是输出完了,都要将走过的路径抹去 
            top--;

        }
    }

}

int main(void){
//自己把迷宫初始化一下;
    for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
            H[i][j]=-1; }
    }
    H[1][1]=H[2][1]=H[2][2]=H[3][2]=H[3][3]=H[3][4]=H[3][5]=H[3][6]=H[3][7]=H[4][2]=H[4][3]=H[4][7]=0;  
    H[5][2]=H[5][3]=H[5][4]=H[5][5]=H[5][6]=H[5][7]=H[6][2]=H[6][6]=H[6][7]=H[7][2]=H[7][3]=H[7][6]=H[7][7]=H[8][3]=H[8][4]=H[8][5]=H[8][6]=H[8][7]=H[8][8]=0;  
    Maze(1,1);
    return 0;

}