首页 > 代码库 > hdu1241 基础BFS
hdu1241 基础BFS
题意:问整个图中有几个油田,油田的八个方向都算同一块。
思路:先找到一个油田,进行BFS搜索,找到一个就标记一个,知道找不到位置。再找一个油田搜索。如此下去就可以找到所有的
#include<cstdio>#include<cstring>#include<queue>struct node{ int x,y; node(int x = 0,int y = 0) : x(x),y(y){}};const int maxn = 200;int dx[8] = {0,1,1,1,-1,-1,0,-1};int dy[8] = {1,1,0,-1,0,-1,-1,1};std::queue<node>q;int vis[maxn][maxn];char map[maxn][maxn];int n,m;void BFS(int i,int j){ q.push(node(i,j)); while(!q.empty()) { int x = q.front().x; int y = q.front().y; q.pop(); for(int i =0;i<8;i++) { int x1 = x + dx[i]; int y1 = y + dy[i]; if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m)continue; if(!vis[x1][y1] && map[x1][y1] == ‘@‘) { vis[x1][y1] = 1; q.push(node(x1,y1)); } } }}int main(){ int i,j; while(scanf("%d%d",&n,&m),n+m) { while(!q.empty())q.pop(); int sum = 0; for(i=0;i<n;i++) { scanf("%s",map[i]); } memset(vis,0,sizeof(vis)); for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(map[i][j] == ‘@‘ && !vis[i][j]) { sum ++; vis[i][j] = 1; BFS(i,j); } } } printf("%d\n",sum); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。