迷宫求解
求迷宫中从入口到出口的所有路径是一个典型的程序设计问题。由于计算机解迷宫时，通常用的是”穷举求解“的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。
为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用'栈'也就是自然而然的事了。
迷宫在计算机中可以用一个二维数组来表示：
int labyrinth[10][10]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1},
};
上面给出的是一个10*10的二维数组，表示迷宫的长宽分别为10。其中，1表示墙，0表示通道。
(1,1)为起点，(8,8)为终点。我们可以在命令行中打印出迷宫的图形：
printf("%c%c",0xa8, 0x80); //打印白色方块，表示墙
printf(" ");//打印空格，表示通道
则上述的数组打印出迷宫为：
迷宫图形
在迷宫中有上下左右四个方向，在此，我们以逆时针方向设定一个寻向的优先级：
| 0 | 1 | 2 | 3 |
|---|---|---|---|
| 向下 | 向右 | 向上 | 向左 |
LabyrinthAnalyze.c利用了前面的C封装的顺序栈对象 用线性表表示的顺序栈
实现了上图展示的迷宫的路径求解问题，并把每一步都打印了出来。
在打印的迷宫图中，
**表示起点与终点；
oo表示足迹；
xx表示走过的死路的足迹。
LabyrinthAnalyze.c文件
#include <stdio.h>
#include <malloc.h>
#include "LinearListStack.h"
int labyrinth[10][10]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1},
};
void copyArray(int a[][10],int b[][10]){
int i,j;
for(i=0;i<10;i++){
for(j=0;j<10;j++){
a[i][j] = b[i][j];
}
}
}
void printLabyrinth(int labyrinth[][10]){
int i,j;
printf("The labyrinth is:\n\n");
for(i=0;i<10;i++){
for(j=0;j<10;j++){
if((i == 1 && j == 1)||(i == 8 && j == 8)){
printf("**");
}else{
if(labyrinth[i][j] == 1){
printf("%c%c",0xa8, 0x80);
}else if(labyrinth[i][j] == 0){
printf(" ");
}else if(labyrinth[i][j] == 2){
printf("oo");
}else if(labyrinth[i][j] == 3){
printf("xx");
}
}
}
printf("\n");
}
}
void labyrinthPath(int labyrinth[][10]){
int labyrinthpath[10][10]; //轨迹图
int current_step = 0; //当前步数
int start_i = 1,start_j = 1; //开始位置
int end_i = 8,end_j = 8; //结束位置
int current_i = start_i,current_j = start_j; //当前位置
int current_direction = 0; //0:向下、1：向右、2：向上、3：向左 逆时针旋转方向，数值小的优先级高
char stack_temp;
char stack_history_i,stack_history_j;
LinearListStack *stack_i = InitLinearListStack();
LinearListStack *stack_j = InitLinearListStack();
copyArray(labyrinthpath,labyrinth);
do{
if(labyrinthpath[current_i][current_j] == 0){ //未走过,且可以走
labyrinthpath[current_i][current_j] = 2; //留下足迹
stack_temp = (char)(current_i+0x30);
stack_i->push(stack_i,&stack_temp);
stack_temp = (char)(current_j+0x30);
stack_j->push(stack_j,&stack_temp);//加入路径
current_step ++;
printLabyrinth(labyrinthpath);
if(current_i == end_i && current_j == end_j) break;//到达终点
}else{
if(stack_i->length(stack_i)){
switch(current_direction){
case 0:
if(labyrinthpath[current_i + 1][current_j] == 0){
stack_i->getTop(stack_i,&stack_history_i);
stack_j->getTop(stack_j,&stack_history_j);
if((stack_history_i != current_i+0x30)||(stack_history_j != current_j+0x30)){
stack_temp = (char)(current_i+0x30);
stack_i->push(stack_i,&stack_temp);
stack_temp = (char)(current_j+0x30);
stack_j->push(stack_j,&stack_temp);//将移出的重新加入路径
}
current_i++;//向下找
current_direction = 0;
}else{
current_direction = 1;
}
break;
case 1:
if(labyrinthpath[current_i][current_j + 1] == 0){
stack_i->getTop(stack_i,&stack_history_i);
stack_j->getTop(stack_j,&stack_history_j);
if((stack_history_i != current_i+0x30)||(stack_history_j != current_j+0x30)){
stack_temp = (char)(current_i+0x30);
stack_i->push(stack_i,&stack_temp);
stack_temp = (char)(current_j+0x30);
stack_j->push(stack_j,&stack_temp);//将移出的重新加入路径
}
current_j++; //向右找
current_direction = 0;
}else{
current_direction = 2;
}
break;
case 2:
if(labyrinthpath[current_i - 1][current_j] == 0){
stack_i->getTop(stack_i,&stack_history_i);
stack_j->getTop(stack_j,&stack_history_j);
if((stack_history_i != current_i+0x30)||(stack_history_j != current_j+0x30)){
stack_temp = (char)(current_i+0x30);
stack_i->push(stack_i,&stack_temp);
stack_temp = (char)(current_j+0x30);
stack_j->push(stack_j,&stack_temp);//将移出的重新加入路径
}
current_i--;//向上找
current_direction = 0;
}else{
current_direction = 3;
}
break;
case 3:
if(labyrinthpath[current_i][current_j - 1] == 0){
stack_i->getTop(stack_i,&stack_history_i);
stack_j->getTop(stack_j,&stack_history_j);
if((stack_history_i != current_i+0x30)||(stack_history_j != current_j+0x30)){
stack_temp = (char)(current_i+0x30);
stack_i->push(stack_i,&stack_temp);
stack_temp = (char)(current_j+0x30);
stack_j->push(stack_j,&stack_temp);//将移出的重新加入路径
}
current_j--;//向左找
current_direction = 0;
}else{
current_direction = 4;
}
break;
case 4://四周均不通
if(labyrinthpath[current_i][current_j] != 1){
labyrinthpath[current_i][current_j] = 3; //死路标记
printLabyrinth(labyrinthpath);
}
stack_i->pop(stack_i,&stack_temp);
current_i = (int)stack_temp-0x30;
stack_j->pop(stack_j,&stack_temp);
current_j = (int)stack_temp-0x30;
current_direction = 0;
break;
}
}
}
}while(stack_i->length(stack_i));
if(stack_i->length(stack_i)){
printf("Maze path:\n");
printf("i:");
stack_i->risePrint(stack_i);
printf("j:");
stack_j->risePrint(stack_j);
}else{
printf("No path found!\n");
}
DestroyLinearListStack(stack_i);
DestroyLinearListStack(stack_j);
}
int main(void)
{
labyrinthPath(labyrinth);
return 0;
}
编译：
gcc LinearListStack.c LinearListStack.h LabyrinthAnalyze.c -o LabyrinthAnalyze
运行LabyrinthAnalyze：
第1步
第2步
第3步
第4步
第5步
第6步
第7步
第8步
第9步
第10步
第11步
第12步
第13步
第14步
第15步
第16步
第17步
第18步
最后输出迷宫的路径：
Maze path:
i:123455566678888
j:111112334555678
i，j表示二维数组的下标[i][j],
该路径可以表示为：
(i,j):(1,1)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(6,3)->(6,4)->(6,5)->(7,5)->(8,5)->(8,6)->(8,7)->(8,8)
网友评论