首页 > 代码库 > 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;}