回溯法——迷宫问题
程序员文章站
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;
}