简单的BFS

86 阅读 0 评论 57 点赞

我是靠谱客的博主悲凉灰狼，最近开发中收集的这篇文章主要介绍简单的BFS，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

洛谷P1162
题意是1是围墙，围墙内的0变2，围墙外的不变。
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
变成下面的
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
思路：
那我们可以在外面矩阵加一圈0，然后把外墙外的0走一遍并记录下来，遇到围墙就不走了，然后输出把没走过的0变成2（围墙内的0）；
这个是上左下右
int xx[] = {1,0,-1,0};
int yy[] = {0,-1,0,1};
写不顺手，下面的也可以
（x+1，y) 向上
（x,y-1）向左
` （x-1，y) 向下
（x，y+1) 向上

我们建立的两个站，判断x,y都可以。
` while (!x.empty())
也可以
while (!y.empty())

#include
#include
#include
using namespace std;

#define ma 40
int n;
bool vis [ma][ma];
int a [ma][ma];
int xx[] = {1,0,-1,0};
int yy[] = {0,-1,0,1};
int main ()
{
cin >>n;
for (int i=1; i<=n; i++)
for (int k=1; k<=n; k++)
cin >> a[i][k];
queue x;
queue y;
vis [0][0]=1;
x.push(0);
y.push(0);
while (!x.empty())
{
for (int i=0; i<n; i++)
{
{
int dx=x.front ()+xx[i];
int dy=y.front ()+yy[i];
if(dx>=0&&dx<=n+1&&dy>=0&&dy<=n+1&&!vis[dx][dy]&&a[dx][dy]==0)
{
x.push (dx);
y.push (dy);
vis [dx][dy]=1;
}
}
}
x.pop();
y.pop();
}
for (int i=1; i<=n; i++)
{
for (int k=1; k<=n; k++)
{
if(!vis[i][k]&&a[i][k]==0)
{
cout << 2 <<’ ‘;
}
else
cout << a[i][k] <<’ ';
}
cout << endl;
}
return 0;
}