前言：关于深度优先搜索和广度优先搜索，莫名又想起了那句话，用空间换取时间。

大部分还是在看别人的文章，自己的见解还不是很足，算法导论上好像有，哪天去看一眼，最先是搜到一篇知乎的文章..那代码写的，血压上来了，还是要一比多家再去认真看文章，算法导论才是标准！

先记录下自己学的，原来是在羊城杯那题需要深度优先搜索，那题并不是经典的走迷宫问题，BFS主要用于最短路径走迷宫，广度优先搜索还没有心情学（最近还有好多加密要手打一份），再干人要坏了。

DFS

这边先记录下对DFS的学习

用着这些思想，打了份走迷宫的DFS（雾）

#include <stdio.h>
#include <stdbool.h>

#define ANS_X 2         //坐标
#define ANS_Y 2
#define BOUNDARY_X 3    //地图边界
#define BOUNDARY_Y 3      
#define MAX 10

int used[BOUNDARY_X][BOUNDARY_Y] = { 0 };               //已使用坐标
int dir[][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };    //移动方式
int best[MAX][MAX];

bool DFS(int used[BOUNDARY_X][BOUNDARY_Y], int x, int y);

int main(void)
{
    int i, j;

    DFS(used, 0, 0);

    for ( i = 0; i < MAX; i++ )
    {
        for ( j = 0; j < MAX; j++ )
        {   
            if ( i == 0 && j == 0 )     //起点
                printf("#");
            else if ( best[i][j] )      //走过的路
                printf("*");
            else
                printf(" ");
        }
        printf("\n");
    }

    return 0;
}

bool DFS(int used[BOUNDARY_X][BOUNDARY_Y], int x, int y)
{
    if ( (x == ANS_X) && (y == ANS_Y) )
    {
        return true;                                       //找到坐标 向上递归（只会发生一次）
    }

    for ( int i = 0; i <= 4; i++ )
    {
        int new_x = x + dir[i][0], new_y = y + dir[i][1];//遍历相邻的坐标
        if ( new_x >= 0 && new_x < BOUNDARY_X && new_y >= 0 && new_y < BOUNDARY_X && used[new_x][new_y] == 0 )
        {

            used[new_x][new_y] = 1;                     //在下一步搜索中 确保当前坐标不会被走到

            if ( DFS(used, new_x, new_y) )              //去新坐标找正确坐标
            {
                printf("(%d,%d)\n", new_x, new_y);      //这边找个栈的ADT不错
                best[new_x][new_y] = 1;                 //标记这是走过的路
                return true;                               //向上递归
            }

            used[new_y][new_x] = 0;                     //设置成false 因为有可能出现在别的路径中
        }
    }

    return false;                                           //本次搜索无解
}

每次打递归都很兴奋！效果图

笔记未完待续…To be continue–>

https://blog.csdn.net/raphealguo/article/details/7523411

https://blog.csdn.net/raphealguo/article/details/7560918