BFS
回顾广度优先搜索
好久没好好学学算法了,今天想写一个八皇后,发现啥也不会了,遂打算重新复习一下,就写了一下今天的广度优先搜索,实现的功能很简单,从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;
}