利用队列求解迷宫 数据结构p93 and p103
#include <iostream> #include <queue> #include <algorithm> #include<stdio.h> #include <stdlib.h> using namespace std; int Maxsize=55; //int mg[99][99]; int mg[11][11]= { {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; typedef struct { int i,j; int pre; } Box; typedef struct { //ElemType data[Maxsize]; //Box data[Maxsize]; Box data[88]; int fro,rear; } QuType; //顺序队类型 void InitQueue(QuType * &q) { q=(QuType *)malloc(sizeof(QuType)); q->fro=q->rear=-1; } void DestroyQueue(QuType * &q) { free(q); } bool QueueEmpty(QuType *q) { return(q->fro==q->rear); } bool enQueue(QuType * &q,Box & e) { if(q->rear==Maxsize-1) return false; q->rear++; q->data[q->rear]=e; return true; } bool deQueue(QuType * &q,Box &e) { if(q->fro==q->rear) return false; q->fro++; e=q->data[q->fro]; return true; } void print(QuType *qu,int fro) { int k=fro,j,ns=0; printf("\n"); do { j=k; k=qu->data[k].pre; qu->data[k].pre; qu->data[j].pre=-1; } while(k!=0); printf("一条迷宫路径如下：\n"); k=0; while(k<Maxsize) { if(qu->data[k].pre==-1) { ns++; printf("\t(%d,%d)",qu->data[k].i,qu->data[k].j); if(ns%5==0) printf("\n"); } k++; } cout << endl; } bool mapath1(int xi,int yi,int xe,int ye) { Box e; int i,j,di,i1,j1; QuType *qu; InitQueue(qu); e.i=xi; e.j=yi; e.pre=-1; enQueue(qu,e); mg[xi][yi]=-1; while(!QueueEmpty(qu)) { deQueue(qu,e); i=e.i; j=e.j; if(i==xe&&j==ye) { print(qu,qu->fro); DestroyQueue(qu); return true; } for(di=0; di<4; di++) { switch(di) { case 0: i1=i-1; j1=j; break; case 1: i1=i; j1=j+1; break; case 2: i1=i+1; j1=j; break; case 3: i1=i; j1=j-1; break; } if(mg[i1][j1]==0) { e.i=i1; e.j=j1; e.pre=qu->fro; enQueue(qu,e); mg[i1][j1]=-1; } } } DestroyQueue(qu); return false; } int main() { int x,y; cin >> x >> y; /*cout << "请输入地图的大小："; cin >> x >> y; for(int i=0; i<x; i++) { for(int j=0; j<y; j++) { cin >> mg[i][j]; } }*/ if(!mapath1(1,1,x,y)) printf("该迷宫没有解\n"); return 1; }