从迷宫入口点（1,1）出发，向四周搜索，记下所有能一步到达的点坐标，然后依次再从这些点出发，然后再记下所有能一步到达的坐标点…依次类推直到能找到迷宫的出口点（m,n）为止，然后从出口点沿搜索点回溯直至入口 这样就能找到迷宫的最短路径，否则无路可走.在搜索过程中必须记下每一个可到达的坐标点，以便从这些点出发继续向四周搜索，由于先到达的点先向下搜索，故引进一个“先进先出”数据结构—队列来保存已到达的点的坐标.
(一)迷宫的数据结构的表示 设迷宫为m行n列,利用maze[m][n]来表示一个迷宫,maze[i][j]=0或1,其中0表示通,1表示不通,当从某点向下试探时有8个方向可试探,而四角的点有3个方向可试探,边缘的点有5个方向可试探,为使问题简化,可用maze[m+2][n+2]来表示迷宫,则每个点都有8个方向一致 迷宫的定义如下:
#define m 6 #define n 8 int maze[m+2][n+2]
(二)试探方向的数据结构的表示 每个坐标点有八个方向可以试探,规定试探顺序:从当前位置向前试探的方向为从正东沿顺时针方向进行.为了简化问题,方便求出新点的坐标,可将八个方向关于x和y的增量存入结构数组move[8]中. move数组定义如下
typedef struct { int x,y; }increase; increase move[8];
(三)队列的设计 可用一个数组作为队列的存储空间,每个空间中存放三个域:x,y,pre. x和y表示所到达点的坐标,pre表示当前队列中队头元素的位置,这样不但记下了到达点的坐标,还记下了它的前驱点.队头元素所指点的八个位置都搜索完毕之后则出队,继续对下一点进行搜索. 队的定义如下:
typedef struct { int x; int y; int pre; }position; typedef struct queue { position data[max]; int front; int rear; }Queue,*pQueue;
数据结构定义
#include<stdio.h> #include<malloc.h> #include<stdlib.h> #define m 6 #define n 8 #define M 3 #define N 1 #define max 100 int maze[m+2][n+2]; //表示迷宫的数据结构 typedef struct { int x; int y; int pre; }position; typedef struct queue { position data[max]; int front; int rear; }Queue,*pQueue; typedef struct { int x; int y; }increase; increase move[8];//定义增量数组函数声明
pQueue init_queue(); void enqueue(pQueue que,int x,int y,int pre); void dequeue(pQueue que); int empty_queue(pQueue que); void init_maze(int maze [m+2][n+2]); void restore(int maze[m+2][n+2]); void init_increase(increase[]); int shortestpath(pQueue que); void printpath(pQueue que);`队列的函数定义
pQueue init_queue() { pQueue que; que=(pQueue)malloc(sizeof(Queue)); while(que==NULL) { printf("没有多余的内存空间！"); exit(-1); } que->front=-1; que->rear=-1; return que; } void enqueue(pQueue que,int x,int y,int pre) { que->rear=(que->rear+1)%max; que->data[que->rear].x=x; que->data[que->rear].y=y; que->data[que->rear].pre=pre; } void dequeue(pQueue que) { if(!empty_queue(que)) que->front=(que->front+1)%max; } int empty_queue(pQueue que) { if(que->rear==que->front) return 1; else return 0; }迷宫和增量数组的函数定义
void init_maze(int (*maze)[n+2]) { for(int i=0;i<m+2;i=i+m+1) {for(int j=0;j<n+2;j++) maze[i][j]=1;} for(int j=0;j<n+2;j=j+n+1) {for(int i=0;i<m+2;i++) maze[i][j]=1; } for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) scanf("%d",&maze[i][j]); } } void init_increase(increase move[8]) { move[0].x=0; move[0].y=1; move[1].x=1; move[1].y=1; move[2].x=1; move[2].y=0; move[3].x=1; move[3].y=-1; move[4].x=0; move[4].y=-1; move[5].x=-1; move[5].y=-1; move[6].x=-1; move[6].y=0; move[7].x=-1; move[7].y=1; }搜索迷宫最短路径函数
int shortestpath(pQueue que) { int x,y,i,j,v; init_maze(maze); init_increase(move); enqueue(que,1,1,-1); maze[1][1]=-1; while(!empty_queue(que)) { x=que->data[que->front+1].x; //找到当前队头元素的位置坐标 y=que->data[que->front+1].y; for(v=0;v<8;v++) //搜索当前位置的8个方向,如果走的通则入队 { i=x+move[v].x; j=y+move[v].y; if(maze[i][j]==0) { enqueue(que,i,j,que->front+1); maze[i][j]=-1; } if(i==m&&j==n) { printpath(que); restore(maze); return 1; } } dequeue(que); //当前位置的8个方向搜索完毕,出队,队头指向下一元素继续搜索 } return 0; } void printpath(pQueue que) //回溯打印最短路径 { position pos; printf("该迷宫的最短路径为：\n"); pos=que->data[que->rear]; printf("(%d,%d)",pos.x,pos.y); pos=que->data[pos.pre]; while(pos.pre!=-1) {printf("<-(%d,%d)",pos.x,pos.y); pos=que->data[pos.pre];} printf("<-(%d,%d)",pos.x,pos.y); } void restore(int maze[m+2][n+2]) //恢复迷宫函数 { for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(maze[i][j]==-1) maze[i][j]=0; } } }主函数
int main() { pQueue que; que=init_queue(); if(!shortestpath(que)) printf("该迷宫无路可走！"); }(6,8)<-(5,7)<-(4,6)<-(4,5)<-(3,4)<-(3,3)<-(2,2)<-(1,1)
迷宫搜索过程
