《2022年迷宫最最短路径 .pdf》由会员分享，可在线阅读，更多相关《2022年迷宫最最短路径 .pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、迷宫最最短路径代码：#include #include #include #include int H, W; int *map; using namespace std; struct PosType int x; int y; ; /*struct ElemType int ord; PosType seat; int di;/1,2,3,4 分别代表 E, S, W, N; ;*/ typedef struct Node struct Node *next; struct Node *prior; PosType seat; *Link; struct Stack Link head;
2、int len; ; void InitStack(Stack &stack) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - stack.len = 0; stack.head = (Link)malloc(sizeof(Link); if(!stack.head) exit(1); stack.head-next = NULL; stack.head-prior = NULL; void Push(Stack &stack,
3、 PosType seat) Link p; p = new Node; p-seat = seat; p-next = stack.head-next; if(stack.head-next)/注意下一个是否为空stack.head-next-prior = p; stack.head-next = p; p-prior = stack.head; bool Pop(Stack &stack, PosType &seat ) Link p; p = stack.head-next; if(p) seat = p-seat; stack.head-next = p-next; if(p-nex
4、t) p-next-prior = p-prior; free(p); return true; return false; bool GetTop(Stack &stack, PosType &seat) if(stack.head-next) Link p = stack.head-next; seat = p-seat; return true; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - return false;
5、void PrintSeat(PosType data) printf(%d %d , data.y, data.x); void StackTraverse(Stack stack, void(*visit)(PosType) Link p, q; for(q = stack.head-next; q-next; q = q-next); for(p = q; p-prior; p = p-prior) visit(p-seat); /printf(n); /=the defination of queue= struct Queue Node *front; Node *rear; ; v
6、oid InitNode(Node &p) p.next = NULL; void InitQueue(Queue &Q) Node *node = (Node *)malloc(sizeof(Node); InitNode(*node); Q.front = node; Q.rear = node; void EnQueue(Queue &Q, PosType seat) Link q; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - -
7、 - - q = (Node *)malloc(sizeof(Node); if(!q) exit(1); InitNode(*q);/because we insert it at the end of the queue, so we need let it point to null q-seat = seat; Q.rear-next = q; Q.rear = q; bool DeQueue(Queue &Q, PosType &seat) if(Q.rear = Q.front) return false; else Node *node = Q.front-next; Q.fro
8、nt-next = node-next; if(!node-next) Q.rear = Q.front; seat = node-seat; free(node); return true; bool QueueEmpty(Queue Q) if(Q.rear = Q.front) return true; else return false; void DestroyQueue(Queue &Q) PosType data; while(Q.rear != Q.front) DeQueue(Q, data); free(Q.rear); free(Q.front); Q.rear = Q.
9、front = NULL; /= 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - bool InRange(PosType seat) if(seat.x W-1 | seat.y H-1) return false; else return true; bool Pass_Mark(Queue &Q, PosType preSeat, PosType curSeat, PosType start) if(mapcurSeat.
10、ycurSeat.x = 0 | (curSeat.x = start.x & curSeat.y = start.y) return false; else if(mapcurSeat.ycurSeat.x = 1 | mapcurSeat.ycurSeat.x mappreSeat.ypreSeat.x+1) mapcurSeat.ycurSeat.x = mappreSeat.ypreSeat.x+1; EnQueue(Q, curSeat); return true; return false; PosType NextPos(PosType seat, int di)/1,2,3,4
11、,5,6,7,8respresent /s, w, n, e, sw, se, nw, ne switch(di) case 1: seat.y+=1; break; case 2: seat.x+=1; break; case 3: seat.x-=1; break; case 4: seat.y-=1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - break; return seat; bool StackEmpty(S
12、tack s) if(s.head-next) return false; return true; bool MazePath(PosType start, PosType end, Stack &stack) mapstart.ystart.x = 1; mapend.yend.x = 1; PosType curpos = start; PosType nextpos, temp; Queue Q; InitQueue(Q); EnQueue(Q, curpos); while(!QueueEmpty(Q) DeQueue(Q, temp); if(temp.y 0)/N nextpos
13、 = NextPos(temp, 4); Pass_Mark(Q, temp, nextpos, start); if(temp.x 0)/W nextpos = NextPos(temp, 3); Pass_Mark(Q, temp, nextpos, start); if(temp.y H-1)/S nextpos = NextPos(temp, 1); Pass_Mark(Q, temp, nextpos, start); if(temp.x 0)/N nextpos = NextPos(temp, 4); if(mapnextpos.ynextpos.x = maptemp.ytemp
14、.x-1) Push(stack, nextpos); findnext = 1; continue; if(temp.x 0)/W nextpos = NextPos(temp, 3); if(mapnextpos.ynextpos.x = maptemp.ytemp.x-1) Push(stack, nextpos); findnext = 1; continue; if(temp.y H-1)/S nextpos = NextPos(temp, 1); if(mapnextpos.ynextpos.x = maptemp.ytemp.x-1) Push(stack, nextpos);
15、findnext = 1; continue; if(temp.x W-1)/E 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - nextpos = NextPos(temp, 2); if(mapnextpos.ynextpos.x = maptemp.ytemp.x-1) Push(stack, nextpos); findnext = 1; continue; Pop(stack, temp); PrintSeat(tem
16、p); while(!StackEmpty(stack) printf(n); Pop(stack, temp); PrintSeat(temp); coutendl; return true; void FindStartEnd(PosType &start, PosType &end) int i, j; for(i = 0; i H; i+) for(j = 0; j W; j+) switch(mapij) case 3: start.x = j; start.y = i; break; case 4: end.x = j; end.y = i; default: break; 名师资
17、料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - void DestroyMap() int i; for(i = 0; i H; i+) free(mapi); free(map); int main() scanf(%d%d, &H, &W); int i, j; map = (int *)malloc(sizeof(int *)*H); for(i = 0; i H; i+) mapi = (int *)malloc(sizeof
18、(int)*W); for(i = 0; i H; i+) for(j = 0; j W; j+) scanf(%d, &mapij); PosType start, end; FindStartEnd(start, end); Stack stack; InitStack(stack); if(!MazePath(start, end, stack) coutthere is no way to reach the endn; DestroyMap(); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -