回顾广度优先搜索

好久没好好学学算法了，今天想写一个八皇后，发现啥也不会了，遂打算重新复习一下，就写了一下今天的广度优先搜索，实现的功能很简单，从N*N的表中找出最大的数(当然不是for的那种)

算法很拉，就拿这篇文章记录以下，我也没搞什么优化

下面是代码

#include <iostream>
#include <queue>

using namespace std;
#define MAX 6

int a[MAX][MAX] = {
    {3,2,5,6,4,90},
    {8,9,2,4,1,2},
    {5,60,4,7,0,5},
    {14,5,3,7,4,6},
    {1,2,3,4,5,7},
    {1,2,3,4,9,7},
};
int b[MAX+1][MAX+1];
int temp;
int sum;

struct location {
    int x;
    int y;
};

queue<location> que;

void judge()
{
    while(!que.empty())
    {
        int x = que.front().x, y = que.front().y;
        location temp;
        if (sum <= a[x][y]) sum = a[x][y];
        if (x == MAX-1 && y == MAX-1) break;
        if ((x + 1 != MAX) && (b[x + 1][y] != 1))
        {
            temp.x = x + 1;
            temp.y = y;
            b[x + 1][y] = 1;
            que.push(temp);
        }
        if ((y + 1 != MAX) && (b[x][y+1] != 1))
        {
            temp.x = x;
            temp.y = y + 1;
            b[x][y+1] = 1;
            que.push(temp);
        }
        que.pop();
    };
    return;
}

int main()
{
    location first = { 0,0 };
    sum = a[0][0];
    que.push(first);
    judge();
    printf("%d", sum);
    return 0;
}

就这样啦，运行后是90

继昨天的算法，稍稍改进以下，就得到了一个算n*n格子有多少种走法的算法

#include <iostream>
#include <queue>

using namespace std;
#define MAX 4

int a[MAX][MAX] = {0};
int b[MAX+1][MAX+1];
int temp;
int n;
int sum;

struct location {
    int x;
    int y;
};

queue<location> que;

void judge()
{
    while(!que.empty())
    {
        int x = que.front().x, y = que.front().y;
        location temp;
        if (x == MAX - 1 && y == MAX - 1) { n++; }
        if ((x + 1 != MAX))
        {
            temp.x = x + 1;
            temp.y = y;
            que.push(temp);
        }
        if ((y + 1 != MAX))
        {
            temp.x = x;
            temp.y = y + 1;
            que.push(temp);
        }
        que.pop();
    };
    return;
}

int main()
{
    location first = { 0,0 };
    sum = a[0][0];
    que.push(first);
    judge();
    printf("%d", n);
    return 0;
}