迷宫（回溯算法）

程序员文章站 2024-03-04 10:24:44

...

要想解决迷宫问题，首先搞明白八皇后，迷宫问题是回溯和贪心的产物。
题目：现有一个迷宫如图：
迷宫（回溯算法）
黄色五角星为迷宫的起点，红色五角星为迷宫的终点。
要求：找到从起点到终点的所有路线。
思路：我们的目的为了到达终点，所以一定要向着终点的方向出发。
因为迷宫的终点在起点的右下角。
所以我们选择路径时先考虑向下走，
走不通考虑向右走，
走不通考虑向上，
最后考虑向左。
这样就会总有一次到达终点。
思路
1、将“小人”放到起点。
2、判断这个方向是否能走，（起始方向向下）
（1）如果能走，走这条路，并记录这条路已经被走过了
（2）如果不能走，
(a)换个方向，重复步骤 2。如果4个方向都不能走，退回上一步的位置，擦掉这条路被走过的记录，并重复步骤2。
3、如果下一步的坐标是终点坐标，说明一条路径已经诞生了。输出这条路径。并退回上一步，重复步骤2中的（a）,继续探索下一条路径。
思考
什么时候“小人”将所有路径走完？
“小人”将起点向上开始走到终点的路径都走完。（此题的迷宫起点向上和向左是没有路的，所以应该是“小人”从起点开始向右走过的路径都走完）
算法实现

首先声明一个数组用来存储方向：

int move[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };//分别代表向下、向右、向上、向左

当前位置的坐标加上指定的数组元素，就是下一步的坐标。
定义迷宫：

Maze[9][10];

为了记录走过的路：定义一个迷宫副本：

copyMaze[9][10];

记录路线（每一步的坐标）：

way[100][2] = { { 1, 1 } };//用来存储路线(将起点坐标添加进去)

约定：
迷宫数组中：
墙为0、路为-1。
具体实现方法：

#include<stdlib.h>
#include<stdio.h>
#include<windows.h>
int Maze[9][10] = { 0 };
int move[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };//分别代表向下、向右、向上、向左
int way[100][2] = { { 1, 1 } };//用来存储路线(将起点坐标添加进去)
int copyMaze[9][10] = { 0 };//用来记录走过的路
int top = 0;//用来记录步数，并用来指向最后一步的坐标
int count = 0;//用来统计有多少种走法
//制作迷宫路线
void makeAMap(){
    //制作迷宫的路线
    Maze[1][1] = Maze[1][2] = -1;
    Maze[2][1] = Maze[2][2] = Maze[2][3] = -1;
    Maze[3][1] = Maze[3][2] = Maze[3][3] = Maze[3][4] = Maze[3][5] = Maze[3][6] = -1;
    Maze[4][3] = Maze[4][1] = Maze[4][4] = Maze[4][6] = -1;
    Maze[5][1] = Maze[5][4] = Maze[5][6] = Maze[5][7] = Maze[5][8] = -1;
    Maze[6][1] = Maze[6][2] = Maze[6][4] = Maze[6][5] = Maze[6][6] = Maze[6][8] = -1;
    Maze[7][6] = Maze[7][7] = Maze[7][8] = -1;
}
//将路径添加到迷宫中
void addWay(){
    int go = top;
    Maze[1][1] = 1;
    for (int tag = top; tag > -1; tag--){
        Maze[way[tag][0]][way[tag][1]] = 1 + go--;
    }
}
//在迷宫删除上一条路径
void delWay(){
    for (int tag = top; tag > -1; tag--){
        Maze[way[tag][0]][way[tag][1]] = -1;
    }
}
//打印迷宫
void printMap(){
    printf("第%d组\n", ++count);
    int num = 0;
    unsigned int block = 32936;
    unsigned int blank = 8224;
    addWay();
    printf("  0 1 2 3 4 5 6 7 8 9\n");
    for (int i = 0; i < 9; i++){
        printf("%d ", num++);
        for (int j = 0; j < 10; j++){
            if (Maze[i][j] == 0){
                printf("%s", &block);
            }
            else if (Maze[i][j] == -1){
                printf("%s", &blank);
            }
            else{
                printf("%2d", Maze[i][j]);
            }
        }
        printf("\n");
    }
    printf("\n\n");
    delWay();
}

void maze(int x, int y){
    for (int i = 0; i < 4; i++){

        int a = x + move[i][0];
        int b = y + move[i][1];

        if (Maze[a][b] && !copyMaze[a][b]){
            //如果有路，并且没有被走过

            copyMaze[a][b] = 1;//走这条路

            //记录这条路已经被走过了
            way[++top][0] = a;
            way[top][1] = b;

            if (a == 7 && b == 8){
                printMap();
            }
            else{
                maze(a, b);
            }
            //回到上一步，并擦除这一步的痕迹
            top--;
            copyMaze[a][b] = 0;
        }
    }
}
int main(void){
    makeAMap();
    copyMaze[1][1] = -1;
    maze(1,1);
    system("pause");
    return 0;
}