求解走迷宫问题

走迷宫问题

1、介绍
      在nxn的方格里填上1和0，其中0表示路可通，1表示墙(不可通)，走迷宫就是在一个起始点开始，从上下左右四个方向寻找为0的方格走，若有多条路，择最优的路径。下面带来的是8x8的迷宫，并输出一个最优解的路径。

2、代码

#include<stdio.h>

#define N 8  //迷宫大小

int maze[N][N] = {{0, 0, 0, 0, 0, 0, 0, 0}, //迷宫
                  {0, 1, 1, 1, 1, 0, 1, 0},
                  {0, 0, 0, 0, 1, 0, 1, 0},
                  {0, 1, 0, 0, 0, 0, 1, 0},
                  {0, 1, 0, 1, 1, 0, 1, 0},
                  {0, 1, 0, 0, 0, 0, 1, 1},
                  {0, 1, 0, 0, 1, 0, 0, 0},
                  {0, 1, 1, 1, 1, 1, 1, 0}};

int fx[4] = {1, 0, -1, 0}, 
    fy[4] = {0, 1, 0, 1}; //用来表示该点四个方向的下一个点

struct {    //队列存储结构
    int x;
    int y;
    int pre;  
} sq[N * N];

int qh, qe; //表示队列头尾

int check(int i, int j) {
    int flag = 1;
    if (i < 0 || i > 7 || j < 0 || j > 7)    //判断越界
        flag = 0;
    if (maze[i][j] == 1 || maze[i][j] == -1)    //maze[i][j]=1，该点不通，为0可通，为-1已经访问过
        flag = 0;
    return flag;
}

void output() { //输出可通路的x、y坐标
    printf("(%d,%d) ", sq[qe].x, sq[qe].y);
    while (sq[qe].pre != 0) {
        qe = sq[qe].pre;
        printf("(%d,%d) ", sq[qe].x, sq[qe].y);
    }
    printf("\n");
}

int search() {
    int i,j,k;
    qh = -1;
    qe = 0;
    maze[0][0] = -1;   //表示已经访问了
    sq[0].pre = 0;     //起始节点入队
    sq[0].x = 0;
    sq[0].y = 0;
    while (qh != qe) {
        qh = qh + 1;
        for (k = 0; k < 4; k = k + 1) { //寻找该点四个方向可通的点
            i = sq[qh].x + fx[k];    //四个方向的x坐标
            j = sq[qh].y + fy[k];    //四个方向的y坐标
            if (check(i, j) == 1) {    //判断是否可通
                qe = qe + 1;
                sq[qe].x = i; //路可通，入队
                sq[qe].y = j;
                sq[qe].pre = qh; //前一个点在队列中的下标
                maze[i][j] = -1; //该点访问过，设置为-1
                if (sq[qe].x == 7 && sq[qe].y == 7) {
                    return 1;    //有解返回1
                }
            }
        }
    }
    return 0;    //无解返回0
}

int main() {
    if (search()) //判断解
    {
        output();    //输出结果
    } else {
        printf("No solution.\n");
    }
}

3、相关文件：Github