老鼠走迷宫问题
题目描述
堆栈的应用有一个相当有趣的问题，就是实验心理学中有名的“老鼠走迷宫”问题。老鼠走迷宫问题的陈述是:假设把只大老 鼠放在一个没有盖子的大迷宫盒的入口处， 盒中有许多墙使得大部分的路径都被挡住而无法前进。老鼠可以按照尝试错误的方法找到出口。不过，这只老鼠必须具备走错路时就会退回来并把走过的路记下来，避免下次重复走同样的路，就这样直到找到出口为止。简单来说，老鼠行进时，必须遵守以下3个原则。
一次只能走一格遇到墙头无法走时，则退回一步找找看是否有其他的路可以走走过的路不会走第二次
思路分析：
首先环境问题如何解决——仿真迷宫如何设计:我们可以采用二维数组map [row] [ col ]来储存，map [row] [ col ] = 1表示有障碍，无法通过，map [row] [ col ] = 0表示可通行。
则如图：
*****1 1 1 1 1 1 1 1 1 1 1 1 1
入口0 0 0 1 1 0 0 0 1 0 0 1 1
*****1 1 0 0 0 0 1 1 0 0 1 1 1
*****1 1 1 1 0 1 1 1 0 1 0 1 1
*****1 1 0 0 0 1 1 0 0 1 0 1 0
*****1 0 0 1 0 1 0 0 1 1 1 1 1
*****1 1 0 1 0 1 0 1 1 0 0 0 0
*****1 1 0 1 1 1 1 1 1 1 1 1 1
******出口
老鼠在模拟运动的过程中，每次最多只有上下左右四个方向可以选择，那么我们可以采用四个 if 条件句来表示。
可以使用链表来记录走过的位置，并且走过的位置元素改为-1，然后将这个位置放入栈中，再进行类似操作。如果遇到障碍，那么就退回上一个岔路口，再选择其他道路。有一个要点：堆栈的顶端元素就是当前老鼠的位置所在。
伪代码
if(往上可以走）{方格编号入栈；往上走；判断是否是出口；}else if(往下可以走）{方格编号入栈；往下走；判断是否是出口；}else if(往左可以走）{方格编号入栈；往左走；判断是否是出口；}else if(往右可以走）{方格编号入栈；往右走；判断是否是出口；}else//都行不通时{删除顶端元素，出栈；往回走；}
源代码
#include<stdio.h>#include<stdlib.h>#define true 1//真值#define EAST MAZE[xi][yi+1] /*定义东方的相对位置*/#define WEST MAZE[xi][yi-1] /*定义西方的相对位置*/#define SOUTH MAZE[xi+1][yi] /*定义南方的相对位置*/#define NORTH MAZE[xi-1][yi] /*定义北方的相对位置*/struct node{int x,y;//y为横轴，x为纵轴 struct node* next;};typedef struct node list;typedef node* link;int MAZE[10][12] ={1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1,0 ,0, 0, 1, 1, 0 ,0 ,0 ,1 ,1 ,1 ,1, 1 ,1 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,1,1 ,1 ,1 ,1 ,0 ,1 ,1 ,1 ,1 ,1 ,0 ,1, 1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1, 1 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,1 ,1 ,0 ,0, 1 ,0 ,0 ,1 ,1 ,1 ,1, 0, 1, 1, 0, 1, 1 ,0 ,1 ,0 ,0 ,0 ,1 ,0 ,1 ,0 ,0 ,1, 1 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,1 ,1,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1};//模拟迷宫void SearchMap(link Pile); //找路函数 void Push(link *Pile,int x,int y);//入栈void Pop(link *Pile,int x,int y);//出栈int JudgeFinal(int x,int y);//判断是否达到出口 int main(){link Pile = (link)malloc(sizeof(list));//定义 int i = 0,j = 0;printf("[迷宫的地模拟图(0表示道路,1表示墙）\n"); //打印出迷宫的路径图for(i=0;i<10;i++){for(j=0;j<12;j++)printf("%2d",MAZE[i][j]); printf("\n");}if(Pile){//不为NULL时 Pile->x = 1;Pile->y = 0;//入口初始化 Pile->next = NULL;MAZE[1][0] = 6;SearchMap(Pile);}elseprintf("申请空间失败\n");printf("---------------------------\n");printf("[6表示老鼠走过的路线]\n"); /*打印出老鼠走完迷宫后的路径图*/printf("---------------------------\n");for(i=0;i<10;i++){for(j=0;j<12;j++)printf("%2d",MAZE[i][j]);printf("\n");}return 0;}void SearchMap(link Pile){int xi = 1,yi = 0;//入口 while(true){if(EAST == 0){yi = yi + 1; Push(&Pile,xi,yi);}else if(WEST == 0) {yi = yi - 1; Push(&Pile,xi,yi); }else if(SOUTH == 0) {xi = xi + 1;Push(&Pile,xi,yi);} else if(NORTH == 0){xi = xi - 1;Push(&Pile,xi,yi);}else//都走不通的时候 {Pop(&Pile,xi,yi); xi = Pile->x;//走回原来的上一个方格点 yi = Pile->y;MAZE[xi][yi] = 6; } if(JudgeFinal(xi,yi))//判断是否达到终点 break; }return ; }void Push(link *Pile,int x,int y){link string = (link)malloc(sizeof(list));string->x = x;string->y = y;string->next = NULL;string->next = *Pile;//*Pile始终指向堆栈顶端元素 位置 *Pile = string; MAZE[x][y] = 6; } void Pop(link *Pile,int x,int y){link string = *Pile;*Pile = (*Pile)->next;free(string);//出栈，去掉这个路径坐标 MAZE[x][y] = 1;//修改为1，避免下一次重复行走 }int JudgeFinal(int x,int y){if( x == 5 && y == 11 )return 1;elsereturn 0; }
动画版本
#include<stdio.h>#include<stdlib.h>#include <graphics.h> //图形库 #include <conio.h>#include <windows.h>#define true 1#define EAST MAZE[xi][yi+1] /*定义东方的相对位置*/#define WEST MAZE[xi][yi-1] /*定义西方的相对位置*/#define SOUTH MAZE[xi+1][yi] /*定义南方的相对位置*/#define NORTH MAZE[xi-1][yi] /*定义北方的相对位置*/struct node{int x,y;//y为横轴，x为纵轴 struct node* next;};typedef struct node list;typedef node* link;int MAZE[10][12] = {1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1,0 ,0, 0, 1, 1, 0 ,0 ,0 ,1 ,1 ,1 ,1, 1 ,1 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,1,1 ,1 ,1 ,1 ,0 ,1 ,1 ,1 ,1 ,1 ,0 ,1, 1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1, 1 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,1 ,1 ,0 ,0, 1 ,0 ,0 ,1 ,1 ,1 ,1, 0, 1, 1, 0, 1, 1 ,0 ,1 ,0 ,0 ,0 ,1 ,0 ,1 ,0 ,0 ,1, 1 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,1 ,1,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1};void SearchMap(link Pile); //找路函数 void Push(link *Pile,int x,int y);//入栈void Pop(link *Pile,int x,int y);//出栈int JudgeFinal(int x,int y);//判断是否达到出口 int main(){link Pile = (link)malloc(sizeof(list));//定义 int i = 0,j = 0;MessageBox(NULL,TEXT("开始智能走迷宫了哦!"),TEXT("提示"),MB_OK);initgraph(360,500); // 初始化，显示一个窗口，窗口宽为390像素，长为550像素setbkcolor(WHITE);// 设置当前绘图背景色for(i = 0;i <= 360;i += 30){for(j = 0;j <= 500;j += 50){if(MAZE[j/50][i/30] == 1){bar(i,j,i+30,j+50);}}}for(i=0;i<10;i++){for(j=0;j<12;j++)printf("%2d",MAZE[i][j]);printf("\n");}if(Pile){//不为NULL时 Pile->x = 1;Pile->y = 0;//入口初始化 Pile->next = NULL;MAZE[1][0] = 6;SearchMap(Pile);}elseprintf("申请空间失败\n");printf("---------------------------\n");printf("[6表示老鼠走过的路线]\n"); /*打印出老鼠走完迷宫后的路径图*/printf("---------------------------\n");for(i=0;i<10;i++){for(j=0;j<12;j++)printf("%2d",MAZE[i][j]);printf("\n");}getch();closegraph(); return 0;}void SearchMap(link Pile){int xi = 1,yi = 0,i = 0,j = 0;//入口 while(true){if(EAST == 0){yi = yi + 1; Push(&Pile,xi,yi);}else if(WEST == 0) {yi = yi - 1; Push(&Pile,xi,yi); }else if(SOUTH == 0) {xi = xi + 1;Push(&Pile,xi,yi);} else if(NORTH == 0){xi = xi - 1;Push(&Pile,xi,yi);}else//都走不通的时候 {Pop(&Pile,xi,yi); xi = Pile->x;//走回原来的上一个方格点 yi = Pile->y;MAZE[xi][yi] = 6;} cleardevice();//清屏for(i = 0;i <= 360;i += 30){for(j = 0;j <= 500;j += 50){if(MAZE[j/50][i/30] == 1){setfillcolor(BROWN);// 设置当前绘图背景色bar(i,j,i+30,j+50);}else if(MAZE[j/50][i/30] == 6){setfillcolor(GREEN);// 设置当前绘图背景色bar(i,j,i+30,j+50);}else if(MAZE[j/50][i/30] == 2){setfillcolor(RED);// 设置当前绘图背景色bar(i,j,i+30,j+50);}}}getch();if(JudgeFinal(xi,yi))//判断是否达到终点 break; }return ; }void Push(link *Pile,int x,int y){link string = (link)malloc(sizeof(list));string->x = x;string->y = y;string->next = NULL;string->next = *Pile;//*Pile始终指向堆栈顶端元素 位置 *Pile = string; MAZE[x][y] = 6;} void Pop(link *Pile,int x,int y){link string = *Pile;*Pile = (*Pile)->next;free(string);//出栈，去掉这个路径坐标 MAZE[x][y] = 2;//修改为1，避免下一次重复行走 }int JudgeFinal(int x,int y){if( x == 5 && y == 11 )return 1;elsereturn 0; }
