迷宮問題設計小結

已知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(!=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，避免回退；