本文共 1794 字,大约阅读时间需要 5 分钟。
迷宫问题一组解:
//迷宫问题解答:
首先需要定义的变量:迷宫M , 迷宫的行R=7 , 迷宫的列C=8 , 还需要定义一个与迷宫M相同的二维数组t(用来表示迷宫这个格子已经走过了,走过赋值为1) , 以及记录方位的二维数组Move[4][2](f方位表示已经在代码中给出注释);
//迷宫问题需要注意的点:
1.首先需要注意的是:记录走过格子的数组t,最主要的作用是防止迷宫绕圈走;
比如:
2.迷宫的回溯问题:
只要这条路可以走,并且与数组t相同位置所对应的数值为0,那么这个位置就可以走,如果以上两个条件不成立,那么这个位置就不能走,需要进行下一个方位的判断,如果四个方位都不能走,就需要回溯,回溯到上一个位置,但是回溯本身还在for循环中,所以,会接着for循环进行下一个方位的判断,看下一个方位是否可以走,不能走继续下一个方位,四个方位判断完之后还是不能走,接着回溯 . . . . . . 知道找到一个下一个位置;
3.迷宫的输出问题:
1) 首先需要找到满足出口的条件才能,准备输出;
2) 如果找到出口return返回整型数字 1,fa之后将返回的值赋给tag;
3) 之后进入if判断,如果tag==1,输出离终点最近的格子位置;
4) 之后继续返回整型数字 1,一直到入口的位置,tag==1不成立,退出当前循环返回 0,if判断条件不成立,退出Maze函数,回到主调,输出出口位置坐标,结束整个程序;
//找到一组解后从出口向入口输出;#include#define R 7 //行;#define C 8 //列;int M[R+2][C+2]= //迷宫'1'表示墙,'0'表示路;{ //0 1 2 3 4 5 6 7 8 9 /*0*/1,1,1,1,1,1,1,1,1,1, /*1*/1,0,0,1,1,1,1,1,1,1, /*2*/1,0,0,0,1,1,1,1,1,1, /*3*/1,0,0,0,0,0,1,1,1,1, /*4*/1,0,1,0,0,1,0,1,1,1, /*5*/1,0,0,1,0,1,0,0,0,1, /*6*/1,1,1,1,0,0,0,1,0,1, /*7*/1,1,1,1,1,1,0,0,0,1, /*8*/1,1,1,1,1,1,1,1,1,1};int t[R+2][C+2]={0}; //与迷宫相同的二维数组,用来表示该条路有没有走;int Move[4][2]= //记录走的方向;{ {1,0}, //向南走; {0,1}, //向东走; {-1,0}, //向北走; {0,-1} //向西走;};//调用迷宫函数;//先找到出口,在从出口向入口进行输出;int Maze(int x,int y){ if(x==7&&y==8) //迷宫出口为(7,8); return 1; for(int i=0;i<4;i++) //判断四个方位是否可以走; { int a=x+Move[i][0]; //表示下一步要走的横坐标; int b=y+Move[i][1]; //表示下一步要走的纵坐标; //M[a][b]是路并且可以走,用数组t判断是否可以走; if(!M[a][b]&&!t[a][b]) //只要走过t数组就标为1; { t[a][b]=1; //表示该条路已经走过了; //最开始用于接受坐标(7,8),表示已经找到出口; int tag=Maze(a,b); if(tag==1) { printf("<--(%d,%d)",a,b); //输出该条路; //返回表示找到出口逐个返回,并且输出每个位置的坐标; return tag; } } } return 0;}int main(void){ printf("迷宫的一条出路为(从出口到入口):\n"); printf("(出口)"); int tag=Maze(1,1); //迷宫入口为(1,1); printf("<--(%d,%d)(入口)\n",tag,tag); return 0;}
//答案截图: