小项目：迷宫

引言

这个迷宫的话就是去年这时候，我记得当时讲这个的时候我还是一脸懵逼，就是事后花时间能够看懂，能够理解，但是自己肯定是不能够实现的，而且觉得这个东西非常的庞大，很困难的样子，然后现在的话，我已经有足够的思维去想，并且能够完全自己一个人去实现了，然后我觉得很好，不多说，上代码。

1.题目描述及思想

给了一个迷宫，然后1代表墙，0代表路，你可以上下左右移动，然后我自己的设计就是，走过的路，能通设置为8，走不通但走过设置为4

			{1, 1, 1, 1, 1, 1, 1, 1, 1},
            {0, 0, 1, 0, 0, 0, 1, 1, 1},
            {1, 0, 1, 1, 1, 0, 1, 1, 1},
            {1, 0, 0, 1, 0, 0, 1, 1, 1},
            {1, 1, 0, 1, 1, 0, 0, 0, 1},
            {1, 0, 0, 0, 0, 0, 1, 0, 1},
            {1, 0, 1, 0, 1, 0, 0, 0, 1},
            {1, 1, 0, 0, 0, 0, 1, 0, 0},
            {1, 1, 1, 1, 1, 1, 1, 1, 1}

2.代码实现

#include<iostream>

using namespace std;

//[0,0] - [9,9]
const int N = 9;
int maze[N][N] = {
            {1, 1, 1, 1, 1, 1, 1, 1, 1},
            {0, 0, 1, 0, 0, 0, 1, 1, 1},
            {1, 0, 1, 1, 1, 0, 1, 1, 1},
            {1, 0, 0, 1, 0, 0, 1, 1, 1},
            {1, 1, 0, 1, 1, 0, 0, 0, 1},
            {1, 0, 0, 0, 0, 0, 1, 0, 1},
            {1, 0, 1, 0, 1, 0, 0, 0, 1},
            {1, 1, 0, 0, 0, 0, 1, 0, 0},
            {1, 1, 1, 1, 1, 1, 1, 1, 1}
};

bool used[N][N];
int dir[4][2] = { 0,-1,1,0,-1,0,0,1};
int endx = 7, endy = 8;

bool dfs(int x, int y)  //代表当前到达的下标
{
    if (x == endx && y == endy)  //如果已经到达终点 返回true
    {
        maze[x][y] = 8;
        used[x][y] = true;
        return true;
    }
    
    for (int i = 0; i < 4; ++i)  //四个方向不断递归
    {
        int a = x + dir[i][0];
        int b = y + dir[i][1];
        if (a < 0 || a >= N || b < 0 || b >= N) continue;  //越界换方向
        if (maze[a][b] == 1 || used[a][b]) continue;  //是墙壁 或者走过了 换方向
        used[a][b] = true;
        maze[a][b] = 8;
        if (dfs(a, b))  //如果能通返回true
        {
            maze[a][b] = 8;
            return true;
        }
        maze[a][b] = 4;  //不通设置为4，然后换个方向
    }
    return false;  //如果4个方向都不行，返回false
}

void Print()
{
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            printf("%4d", maze[i][j]);
        }
        puts("");
    }
    puts("");
}

int main()
{
    Print();
    used[1][0] = true;
    maze[1][0] = 8;
    dfs(1, 0);
    Print();

    return 0;
}