迷宫问题设计小结

　　已经知道int maze[5][5]引流矩阵表明的谜宫，求得一条(0,0)至(4,4)的途径；

　　构思：

　　1）双向链表储存，踏过途径；

　　2）递归函数char shortest_path(position*currrentpos, position* despos);完成搜索

　　递归函数char shortest_path()的回到状况：

　　1.在该连接点，试着过 右、下、左、上 四个方位，都没法走通，该连接点是条死胡同， 则return 'n'; 退回到上一连接点，在上一节点找寻别的可走的路；

　　2.已经抵达终点despos，return 'y'; 递归法回到 'y'，直到第一次启用char shortest_path()以后，完毕递归函数；

　　1 #include <stdio.h> 2 #include <stdlib.h> 3 4 typedef struct { 5 int _x; //行 6 int _y; //列 7 }position; //连接点座标信息内容，储存途径 8 9 typedef struct _node{ 10 position _pos; 11 struct _node *next; 12 struct _node *pre; 13 }node; 14 15 typedef struct{ 16 node* head; 17 node* tail; 18 }path; //路径的head、tail，浏览途径 19 20 int maze[5][5]={ 21 0,1,0,0,0, 22 0,1,1,1,0, 23 0,0,0,0,0, 24 0,1,0,1,1, 25 0,1,0,0,0, 26 }; 27 28 int offset[4][2]={ 29 0,1, 30 1,0, 31 0,-1, 32 -1,0, 33 };//右、下、左、上 34 35 path path; //路径 36 37 void step_forward(int pos_x,int pos_y) //前行 38 { 39 node* node = (node*)malloc(sizeof(node)); 40 if(node!=null) 41 { 42 node->_pos._x=pos_x; 43 node->_pos._y=pos_y; 44 node->pre=null; 45 node->next=null; 46 if(path.tail!=null) 47 { 48 path.tail->next=node; 49 node->pre=path.tail; 50 path.tail=node; 51 maze[node->_pos._x][node->_pos._y]=-1; 52 } 53 } 54 } 55 56 void step_backforward() 57 { 58 if(path.tail!=null) 59 { 60 node* newtail=path.tail->pre; 61 path.tail->pre->next=null; 62 free(path.tail); 63 path.tail=newtail; 64 } 65 } 66 char is_can_go(int pos_x, int pos_y) 67 { 68 if(pos_x < 0 || pos_x > 4 69 || pos_y < 0 ||pos_y > 4 70 || (maze[pos_x][pos_y]!=0)) 71 return 'n'; //跃出地形图界限，或是是墙，或者是死胡同，回到'n' 72 // if(path.tail->pre!=null&&(path.tail->pre->_pos._x == pos_x && path.tail->pre->_pos._y==pos_y)) 73 // return 'n'; //方位是回到的方位，回到'n' 74 return 'y'; //别的回到'y' 75 } 76 77 char shortest_path(position* currentpos,position* despos) 78 { 79 int i; 80 if(currentpos->_x == despos->_x && currentpos->_y == despos->_y) //假如已经抵达终点，退回 81 return 'y'; 82 for(i=0;i<4; i) 83 { 84 int newpos_x=currentpos->_x offset[i][0]; 85 int newpos_y=currentpos->_y offset[i][1]; 86 if(is_can_go(newpos_x,newpos_y)=='y') //假如所在位置，可以挪动，则移动格子 87 { 88 step_forward(newpos_x,newpos_y); 89 currentpos->_x=newpos_x; 90 currentpos->_y=newpos_y; 91 if('y'==shortest_path(currentpos,despos)) //已经抵达终点站，则回到'y' 92 return 'y'; 93 else //不然，退回 94 { 95 step_backforward(); 96 currentpos->_x=path.tail->_pos._x; 97 currentpos->_y=path.tail->_pos._y; 98 } 99 }100 }101 return 'n';102 }103 104 void initialize()105 {106 path.head=(node*)malloc(sizeof(node));107 path.head->next=null;108 path.head->pre=null;109 path.head->_pos._x=0;110 path.head->_pos._y=0;111 path.tail=path.head;112 maze[0][0]=-1;113 }114 115 void print_path()116 {117 node *node_ptr;118 node_ptr=path.head;119 while(node_ptr!=null)120 {121 printf("(%d, %d)\n",node_ptr->_pos._x,node_ptr->_pos._y);122 node_ptr=node_ptr->next;123 }124 }125 126 int main()127 { 128 position* currentpos;129 position*despos;130 initialize();131 132 currentpos=(position*)malloc(sizeof(position));133 currentpos->_x=0;134 currentpos->_y=0;135 136 despos=(position*)malloc(sizeof(position));137 despos->_x=4;138 despos->_y=4;139 140 shortest_path(currentpos,despos);141 print_path();142 system("pause");143 return 0;144 }

　　存在的不足：编码有点儿杂乱。

　　留意点：

　　1.递归函数，在什么时候回到，如何回到。

　　2.在返回'n'时，因为char* currentpos是指针变量，具体数据储存在堆地区，已经被改动，必须再次将tail所对准的堆地区的值拷贝给currentpos。

　　3.step_forward函数公式，前进一步时，必须maze[][]中相匹配项取值为-1，防止退回；