首页 > 代码库 > [vijos]1051送给圣诞夜的极光<BFS>
[vijos]1051送给圣诞夜的极光<BFS>
送给圣诞夜的极光
题目链接：https://www.vijos.org/p/1051
这是一道很水很水的宽搜水题，我主要是觉得自己在搜素这一块有点生疏于是随便找了一题练手，找到这么一道水题，原本以为可以一次过的，但是状况百出，我并不是很擅长bfs，我以前一直用的Pascal写bfs，但是Pascal没有队列，所以没有c++方便，所以这题我就直接用队列做了，然后完美的炸空间炸时间，后来改成递归调用才通过
思路：这一道题和一道宽搜入门题很像，基本上是一样的，这道题叫细胞个数
链接：http://codevs.cn/problem/3492
这两个题的区别是，前者要找自己周围的12个位置，后者只找自己周围上下左右四个位置，这题的关键点也就是找到这12个位置，其他就是那道细胞的做法，寻找一个为‘#’的点，以这个点向周围可扩展区域扩展，每到一个扩展点就把这个点变成‘-’，直到不能扩展，然后继续寻找为‘#’的点
方法不用多说，先看看我这超时又爆内存的队列bfs吧
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cstdlib> 6 #include<cmath> 7 #include<queue> 8 #define maxn 105 9 using namespace std;10 11 int map[maxn][maxn];12 int n,m,tot;13 14 struct node{15 int x,y;16 };17 18 const int dx[]={0,-1,-1,0,1,1,1,0,-1,-2,0,2,0};19 const int dy[]={0,0,1,1,1,0,-1,-1,-1,0,2,0,-2};20 21 int main()22 {23 scanf("%d%d\n",&n,&m);24 char s[maxn];25 for(int i=1;i<=n;i++)26 {27 scanf("%s",s+1);28 for(int j=1;j<=m;j++)29 {30 if(s[j]==‘#‘)map[i][j]=1;31 }32 }33 34 queue<node>q;35 for(int i=1;i<=n;i++)36 {37 for(int j=1;j<=m;j++)38 {39 if(map[i][j]==1)40 {41 tot++;42 q.push((node){i,j});43 while(!q.empty())44 {45 node v=q.front();46 q.pop();47 map[v.x][v.y]=0;48 for(int k=1;k<=12;k++)49 {50 int nx=v.x+dx[k],ny=v.y+dy[k];51 if(map[nx][ny]==1&&nx>=1&&nx<=n&&ny>=1&&ny<=m)52 {53 q.push((node){v.x+dx[k], v.y+dy[k]});54 } 55 }56 57 }58 }59 }60 }61 62 printf("%d",tot);63 }
个人觉得队列可能容易理解一些，但是队列方法看懂了，递归也可以看懂
AC代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cstdlib> 6 #include<cmath> 7 #include<queue> 8 #define maxn 105 9 using namespace std;10 11 int map[maxn][maxn];12 int n,m,tot;13 const int dx[]={0,-1,-1,0,1,1,1,0,-1,-2,0,2,0};14 const int dy[]={0,0,1,1,1,0,-1,-1,-1,0,2,0,-2};15 16 void bfs(int x,int y)17 {18 map[x][y]=0;19 for(int i=1;i<=12;i++)20 {21 int nx=x+dx[i];22 int ny=y+dy[i];23 if(map[nx][ny]==1&&nx>=1&&nx<=n&&ny>=1&&ny<=m)24 {25 bfs(nx,ny);26 }27 }28 }29 30 int main()31 {32 scanf("%d%d",&n,&m);33 char a;34 for(int i=1;i<=n;i++)35 for(int j=1;j<=m;j++)36 {37 cin>>a;38 if(a==‘#‘)map[i][j]=1;39 }40 for(int i=1;i<=n;i++)41 for(int j=1;j<=m;j++)42 {43 if(map[i][j]==1)44 {45 tot++;46 bfs(i,j);47 }48 } 49 cout<<tot;50 }
[vijos]1051送给圣诞夜的极光<BFS>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。