已知int maze[5][5]矩阵表示的迷宫，求解一条(0,0)至(4,4)的路径；
思路：
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(!=null) 47 { 48 ->next=node; 49 node->pre=; 50 =node; 51 maze[node->_pos._x][node->_pos._y]=-1; 52 } 53 } 54 } 55 56 void step_backforward() 57 { 58 if(!=null) 59 { 60 node* newtail=->pre; 61 ->pre->next=null; 62 free(); 63 =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(->pre!=null&&(->pre->_pos._x == pos_x && ->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=->_pos._x; 97 currentpos->_y=->_pos._y; 98 } 99 }100 }101 return 'n';102 }103 104 void initialize()105 {106 =(node*)malloc(sizeof(node));107 ->next=null;108 ->pre=null;109 ->_pos._x=0;110 ->_pos._y=0;111 =;112 maze[0][0]=-1;113 }114 115 void print_path()116 {117 node *node_ptr;118 node_ptr=;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。
_forward函数，前进一步时，需要maze[][]中对应项赋值为-1，避免回退；