BFS走迷宫

今天上午考完CET4，终于可以暂时放下英语好好的研究算法了

本来想复习复习dfs结果看见了别人写的走迷宫，心生羡慕，那我自己也写一个吧

程序如下

#include <iostream>
#include <queue>

using namespace std;

#define MAX 10//MAX为地图大小

int a[MAX][MAX] = {
    {1,1,1,1,1,1,1,1,1,1},
    {0,1,1,0,0,0,1,0,1,1},
    {0,1,1,1,0,0,1,1,1,1},
    {0,1,0,0,0,0,1,0,0,0},
    {0,1,1,1,1,1,0,0,0,0},
    {0,1,1,0,1,1,1,0,0,0},
    {0,1,0,0,1,1,1,0,0,0},
    {0,1,1,0,0,0,1,0,0,0},
    {0,1,0,0,0,1,1,0,0,0},
    {0,1,1,0,0,1,1,1,1,1},
};//地图，1为可走，0不可走
int b[MAX][MAX] = { 0 };//记录数组
int temp;
int sum;

struct location 
{
    int x;
    int y;
    int store[100][100];
};

queue<location> que;

void judge()
{
    while(!que.empty())
    {
        int x = que.front().x, y = que.front().y;
        que.front().store[x][y] = 1;
        b[x][y] = 1;
        if (x == MAX - 1 && y == MAX - 1)
        {
            for (int i = 0; i <= MAX - 1; i++)
            {
                for (int j = 0; j <= MAX - 1; j++)
                    printf("%d  ", que.front().store[i][j]);
                printf("\n");
            }
            printf("\n");
        }
        if ((y + 1 < MAX) && (a[x][y+1]) && (!b[x][y + 1]))
        {
            que.front().y = y + 1;
            que.front().x = x;
            que.push(que.front());
        }
        if ((x + 1 < MAX) && (a[x + 1][y]) && (!b[x + 1][y]))
        {
            que.front().x = x + 1;
            que.front().y = y;
            que.push(que.front());
        }
        if ((y > 0) && a[x][y-1] != 0 && b[x][y - 1] != 1)
        {
            que.front().y = y - 1;
            que.front().x = x;
            que.push(que.front());
        }
        if ((x > 0) && a[x-1][y] != 0 && b[x - 1][y] != 1)
        {
            que.front().x = x - 1;
            que.front().y = y;
            que.push(que.front());
        }
        que.pop();
    };
    return;
}

int main()
{
    location *first = (location*)malloc(sizeof(location));
    first->x = 0;
    first->y = 0;
    for (int i = 0; i <= MAX; i++)
        for (int j = 0; j <= MAX; j++)
            first->store[i][j] = 0;
    //不懂为什么申请了内存空间后，struct里面数组初始化无效所以只能在这里用for初始化了
    first->store[0][0] = 1;
    que.push(*first);
    judge();
    return 0;
}

输入为n*n的地图

输出为解法，如下图

这只是不到3个小时写的粗品，可能有很多不足的地方，但是看见它能跑起来，心中已经很开心了

记得以前在OJ上面做过的一道题，给一个n*n大小的格子，每个格子有一个值，从左上走到右下，哪条路线加起来的和最大，当时那个程序我是用递归+回溯写的，因为以前对于BFS的掌握不好，所以也不经常用

现在终于用BFS实现了类似的功能

也是遇到了一些问题，比如

为什么申请了内存空间后，struct里面数组初始化无效之类的

但是我感觉了解了这个算法的大致架构，思路，其实还是最重要的

就这样啦，继续努力