BFS模板【洛谷P1162】

奉上题目链接啦：https://www.luogu.org/problemnew/show/P1162

一开始是懵的，这咋搜啊，在圈里咋限定方向啊，这咋做啊！！？？？？

在队友@TDD的启发下，原来我们反其道而行之，题目要求在圈里填数字，我们从四条边向图里面搜，把圈外的都填上-1，最后把0当成2输出，就OK啦！！！

咦？怎么输出出来还是和原来的一样，怎么没有2啊？？？？？

哦哦哦，起点又忘标记了

代码代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int maxn = 35;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int G[maxn][maxn];
int n;
void init()
{
memset(G,0,sizeof(G));
}
void bfs(int x,int y)
{
queue<pair<int,int> > q;
q.push(P(x,y));
while(!q.empty())
{
int nx = q.front().first;
int ny = q.front().second;
q.pop();
for(int i=0;i<4;i++)
{
int nowx = nx+dx[i];
int nowy = ny+dy[i];
if(nowx>=1 && nowx<=n && nowy>=1 && nowy<=n)
{
if(!G[nowx][nowy])
{
G[nowx][nowy] = -1;
q.push(P(nowx,nowy));
}
}
}
}
}
int main()
{
while(cin>>n)
{
init();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>G[i][j];
}
}
for(int i=1;i<=n;i++)
{
if(G[i][1]==0)
{
G[i][1] = -1;
bfs(i,1);
}
}
for(int i=1;i<=n;i++)
{
if(G[1][i]==0)
{
G[1][i] = -1;
bfs(1,i);
}
}
for(int i=1;i<=n;i++)
{
if(G[i][n]==0)
{
G[i][n] = -1;
bfs(i,n);
}
}
for(int i=1;i<=n;i++)
{
if(G[n][i]==0)
{
G[n][i] = -1;
bfs(n,i);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(G[i][j]==0)
{
cout<<"2";
}
else if(G[i][j]==-1)
{
cout<<"0";
}
else
{
cout<<G[i][j];
}
if(j<n)
{
cout<<" ";
}
}
cout<<endl;
}
}
return 0;
}

有时候思想被限定死了，这道题可能永远做不出来。

最后

以上就是风中母鸡为你收集整理的BFS模板【洛谷P1162】的全部内容，希望文章能够帮你解决BFS模板【洛谷P1162】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。