蓝桥杯算法提高VIP-学霸的迷宫（BFS与DFS解法）——看到没人用C语言决定写这个题解（纯c手搓队列）

解题思路:
一眼即可看出为BFS最短路径问题，用DFS只不过是为了娱乐（DFS必超时）
注意事项:

BFS：

//用bfs遍历需要用到队列

//bfs需要标记，无论是它是否四个方向都能走还是只能向下和向右走都要标记，这样才快,才能省内存

//注意字典序最小

DFS：这题虽然是走迷宫但是却需要标记因为可以走四个方向所以会出现原地兜圈的情况

参考代码:

BFS:

#include
#include
#include
#define MAX 1500
//用bfs遍历需要用到队列
//bfs需要标记，无论是它是否四个方向都能走还是只能向下和向右走都要标记，这样才快,才能省内存
//犯错在没有注意到字典序最小
int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}}; //根据字典序最小来排DLRU
bool book[MAX][MAX]; //标记
int n,m;  //长和宽
int map[MAX][MAX];
typedef struct node
{
    int x;
    int y;
    int step;
    char path[MAX];
    struct node *next;
}Node;   //构造链表
typedef struct
{
    Node * front;   //头指针
    Node * rear;    //尾指针
    int size;
} Queue;  //构造队列
void InitQueue(Queue *q)
{
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}
bool QueueIsEmpty(Queue *q)
{
    if(q->size==0)
        return true;
    else
        return false;
}
void DeQueue(Queue *q,Node *temp)   //删除队列头的元素,并把其赋给temp
{
   Node *psave = q->front;
   q->front = q->front->next;
   *temp = *psave;    //把它的值赋到地址上而不是使temp的地址成为它不然free后没了
   q->size--;
   if(QueueIsEmpty(q))
    q->rear = NULL;    //当队列已空
   free(psave);
}
void EnQueue(Queue *q,int x,int y,int step,char move,char path[])  //将元素插入队列尾
{
    Node *pnew = (Node *)malloc(sizeof(Node));
    pnew->next = NULL;
    pnew->step = step;
    pnew->x = x;
    pnew->y = y;
    for(int j=0;jpath[j]=path[j];
    pnew->path[step] = move;
    if(QueueIsEmpty(q))
        q->front=pnew;
    else
        q->rear->next=pnew;
    q->rear=pnew;
    q->size++;
}
/*void FreeAll(Queue *q)
{
    Node temp;
    while(!QueueIsEmpty(q))
        DeQueue(q,&temp);
}*/
void BFS(int x,int y,int step)
{
    Queue q;
    char move[4]={'D','L','R','U'};
    Node temp;
    int i;
    InitQueue(&q);
    EnQueue(&q,x,y,step,'F',"F");
    while(!QueueIsEmpty(&q))
    {
        DeQueue(&q,&temp);
        if(temp.x==n-1 && temp.y==m-1)
        {
            printf("%d\n",temp.step);
            for(int j=1;j<=temp.step;j++)
                printf("%c",temp.path[j]);
            break;
        }
        for(i=0;i=0&&yy>=0&&xx<n&&yy<m&&!book[xx][yy]&&!map[xx][yy])
            {
                book[xx][yy]=true; //需要标记不然内存超限
                EnQueue(&q,xx,yy,temp.step+1,move[i],temp.path);
            }
        }
    }
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        scanf("%1d",&map[i][j]);
    BFS(0,0,0);
    return 0;
}

DFS:

#include
#include
#define MAX 1000
//注意:这题虽然是走迷宫但是却需要标记因为可以走四个方向所以会出现原地兜圈的情况
int map[MAX][MAX];  //存放地图
int book[MAX][MAX];
char path[MAX],path_min[MAX];    //保存走过的路
int min_count=10000,count;  //记录最短路径长度和每次dfs的路径长度
int n,m;
void dfs(int x,int y)
{
    int i;
    if(x==n && y==m)
    {
        if(count<min_count)
        {
            min_count=count;
            for(i=1;i<=count;i++)
                path_min[i]=path[i];
        }
        return;
    }
    for(i=1;i1 && i==1 && !map[x][y-1] && !book[x][y-1])  //向左走
        {
            count++;
            book[x][y-1]=1;
            path[count]='L';
            dfs(x,y-1);
            book[x][y-1]=0; //同下
            count--; //发现走不通或回溯到此恢复count的计数
        }
        else if(y1 && i==3 && !map[x-1][y] && !book[x-1][y])  //向上走
        {
            count++;
            path[count]='U';
            book[x-1][y]=1;
            dfs(x-1,y);
            book[x-1][y]=0;
            count--;
        }
        else if(x<m && i==4 && !map[x+1][y] && !book[x+1][y]) //向下走
        {
            count++;
            book[x+1][y]=1;
            path[count]='D';
            dfs(x+1,y);
            book[x+1][y]=0;
            count--;
        }
    }
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
         scanf("%1d",&map[i][j]);
    dfs(1,1);
    printf("%d\n",min_count);
    for(i=1;i<=min_count;i++)
        printf("%c",path_min[i]);
    return 0;
}