队列完成迷宫路径搜索（C语言）

• 题目概述
• • 问题分析
  • 算法设计
  • 初始化地图
  • 搜索迷宫路径
  • 完整代码

迷宫问题。假设迷宫由m行n列构成，有一个入口和一个出口，入口坐标为（1，1），出口坐标为（m，n），试设计并验证以下算法：找出一条从入口通往出口的路径，或报告一个“无法通过”的信息。

(1) 用C语言实现顺序存储结构上队列的基本操作，然后利用该队列的基本操作找出迷宫的一条最短路径。

(2) 设计一个二维数组MAZE[m+2][n+2]表示迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE[1][1]、MAZE[m][n]分别为迷宫的入口和出口。

(3) 输入迷宫的大小m行和n列，动态生成二维数组；由随机数产生0或1，建立迷宫，注意m*n的迷宫需要进行扩展，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙。

(4) 要求输出模拟迷宫的二维数组；若存在最短路经，则由出口回溯到入口（出队列并利用栈实现），再打印从入口到出口的这条路径，例如(1,1)，……，(i,j)，……，(m,n)；若没有路径，则打印“No path!”。

(5)迷宫的任一位置(i,j)上均有八个可以移动的方向，用二维数组Direction存放八个方向上的位置偏移量。

Direction[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};

(6)为避免出现原地踏步的情况为了标志已经通过的位置，采用一个标志数组MARK[m+2][n+2]，初值均为0，在寻找路径的过程中，若通过了位置(i,j)，则将MARK[i][j]置为1。

(7) 为了记录查找过程中到达位置(i,j)及首次到达(i,j)的前一位置(i_pre,j_pre)，需要记住前一位置(i_pre,j_pre)在队列中的序号pre，即队列中数据元素应该是一个三元组(i,j,pre)。

(8) 搜索过程简单描述如下：将入口MAZE[1][1]作为第一个出发点，依次在八个方向上搜索可通行的位置，将可通行位置(i,j,pre)入队，形成第一层新的出发点，然后依次出队，即对第一层中各个位置分别搜索它所在八个方向上的可通行位置，形成第二层新的出发点，…，如此进行下去，直至达到出口MAZE[m][n]或者迷宫所有位置都搜索完毕为止。

题目要求随机生成迷宫，并用队列完成迷宫的路径查找，每一个队列元素都是一个三元组；三元组为结点的行列坐标和前驱结点。
所以可以得到该题的主要函数。首先需要实现迷宫的初始化，队列的元操作和迷宫的路径搜索。每一个节点在搜索的过程中按照：左→左上→上→右上→右→右下→下→左下，顺序搜索。

在一开始，先将迷宫入口(1,1)入队，对它周围八个方向进行搜索，如果结点可通，就将其入队并在标记数组中标记为1，记为该节点已经搜索。再将队首元素出队，获取它的坐标值，再进行搜索。直到队首元素的坐标为出口坐标。

将边界设置为1，路径在1，0两数随机生成，入口出口都置为0。

void creatMap(int map[][N + 2],int mark[][N + 2]){
    static unsigned int seed = 0;
    seed++;
    srand((unsigned) time(NULL) + seed * seed);
    for (int i = 0; i < M + 2 ; ++i) {
        for (int j = 0; j < N + 2; ++j) {
            if(i == 0 || i == M + 1 || j == 0 || j == N + 1 ){
                map[i][j] = 1;
            }
            else{
                map[i][j] = rand() % (1 - 0 + 1) + 0;
            }
            mark[i][j] = 0;
        }
    }
    map[1][1] = 0;
    map[M][N] = 0;
}

*
bool FindWay(int xi, int yi, int xe, int ye,int map[][N + 2],int mark[][N + 2]){
    int i, j, di;
    SqQueue * sqQueue = malloc(sizeof(SqQueue));
    InitQueue(sqQueue);
    Queue q = {xi,yi,-1};	//将入口的前驱下标置为-1，在打印路径时会用到
    Enqueue(sqQueue,q);		//入口结点入队
    mark[xi][yi] = 1;
    while(EmptyQueue(sqQueue)){
        Dequeue(sqQueue, &i, &j);//队首元素出队，i,j 为其坐标（变参）
        if (i == xe && j == ye){
            print(sqQueue, sqQueue->front,mark,map);
            return true;
        }
        for (int k = 0; k < 8; ++k) {
            Queue next = {i + Direction[k][0],j + Direction[k][1],sqQueue->front};
            if(map[next.i][next.j] == 0 && mark[next.i][next.j] == 0){
                Enqueue(sqQueue,next);
                mark[next.i][next.j] = 1;
            }
        }
    }
    return false;
}

#include
#include 
#include 
#include 

#define MaxSize 100
#define M 8
#define N 8

typedef struct{
    int i;
    int j;
    int pre;
} Queue;

typedef struct Queue
{
    Queue Queue[MaxSize];
    int front;
    int rear;
}SqQueue;

int Direction[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};


void Dequeue(SqQueue *sqQueue, int *i, int *j) {
    sqQueue->front++;
    (*i) = sqQueue->Queue[sqQueue->front].i;
    (*j) = sqQueue->Queue[sqQueue->front].j;
}

void Enqueue(SqQueue *sqQueue,Queue queue) {
    sqQueue->rear++;
    sqQueue->Queue[sqQueue->rear] = queue;
}


void creatMap(int map[][N + 2],int mark[][N + 2]){
    static unsigned int seed = 0;
    seed++;
    srand((unsigned) time(NULL) + seed * seed);
    for (int i = 0; i < M + 2 ; ++i) {
        for (int j = 0; j < N + 2; ++j) {
            if(i == 0 || i == M + 1 || j == 0 || j == N + 1 ){
                map[i][j] = 1;
            }
            else{
                map[i][j] = rand() % (1 - 0 + 1) + 0;
            }
            mark[i][j] = 0;
        }
    }
    map[1][1] = 0;
    map[M][N] = 0;
}

void printMap(int a[M + 2][N + 2]){
    for (int i = 0; i < M + 2; ++i) {
        for (int j = 0; j < N + 2; ++j) {
            printf("%d   ",a[i][j]);
        }
        printf("n");
    }
}


void print(SqQueue * q, int front1,int mark[][N + 2],int map[][N + 2]){
    mark[M][N] = 2;
    for(int i = front1;i > 0;i = q->Queue[i].pre){
        printf("(%d,%d)",q->Queue[i].i,q->Queue[i].j);
        if(q->Queue[i].i != M && q->Queue[i].j != N){
            printf("->");
        }
        map[q->Queue[i].i][q->Queue[i].j] = 3;
    }
}

void InitQueue(SqQueue *sqQueue) {
    sqQueue->rear = 0;
    sqQueue->front = 0;
}

bool EmptyQueue(SqQueue * sqQueue){
    if(sqQueue->front != sqQueue->rear){
        return true;
    } else{
        return false;
    }
}


bool FindWay(int xi, int yi, int xe, int ye,int map[][N + 2],int mark[][N + 2]){
    int i, j, di;
    SqQueue * sqQueue = malloc(sizeof(SqQueue));
    InitQueue(sqQueue);
    Queue q = {xi,yi,-1};
    Enqueue(sqQueue,q);
    mark[xi][yi] = 1;
    while(EmptyQueue(sqQueue)){
        Dequeue(sqQueue, &i, &j);
        if (i == xe && j == ye){
            print(sqQueue, sqQueue->front,mark,map);
            return true;
        }
        for (int k = 0; k < 8; ++k) {
            Queue next = {i + Direction[k][0],j + Direction[k][1],sqQueue->front};
            if(map[next.i][next.j] == 0 && mark[next.i][next.j] == 0){
                Enqueue(sqQueue,next);
                mark[next.i][next.j] = 1;
            }
        }
    }
    return false;
}

int main(){
    int map[M + 2][N + 2];
    int mark[M + 2][N + 2];
    creatMap(map,mark);
    printMap(map);		//先打印迷宫
    if (!FindWay(M, N, 1, 1,map,mark))
        printf("No path!");	//没找到路径打印No path!
    printf("nn");
    printMap(map);		//再次打印迷宫，3为最终路径
    printf("nn");
    printMap(mark);		//打印标记数组，观察代码执行情况
    return 1;
}