---

title: HDU-1241
categories:

• ACM
• BFS
  tags:
• 图的连通区域
• 水题
  date: 2020-02-23 19:57:05

---

简单BFS，找到一个入队点将所有可达的区域置为不可达

题目

油藏

*时间限制：2000/1000 MS（Java /其他）内存限制：65536/32768 K（Java /其他）
提交总数：58896接受提交：33745
*

问题描述

GeoSurvComp地质勘测公司负责检测地下油藏。GeoSurvComp一次处理一个大矩形区域的土地，并创建一个将土地划分为多个正方形图的网格。然后，它使用传感设备分别分析每个地块，以确定该地块是否包含油。包含油的地块称为矿穴。如果两个凹坑相邻，则它们是同一油藏的一部分。积油可能很大，可能包含许多凹穴。您的工作是确定网格中包含多少种不同的油藏。

输入值

输入文件包含一个或多个网格。每个网格均以包含m和n的行开始，网格中的行和列数为m和n，并用单个空格分隔。如果m = 0，则表示输入结束；否则，输入0。否则为1 <= m <= 100和1 <= n <=100。紧随其后的是m行，每行n个字符（不计算行尾字符）。每个字符对应一个地块，要么是代表无油的“ *”，要么是代表油囊的“ @”。

输出量

对于每个网格，输出不同的油藏数量。如果两个不同的油藏在水平，垂直或对角线上相邻，则它们是同一油藏的一部分。积油最多可容纳100个口袋。

样本输入

1 1 
* 
3 5 
* @ * @ * 
** @ ** 
* @ * @ * 
1 8 
@@ **** @ * 
5 5 
**** @ 
* @@ * @ 
* @ ** @ 
@@@ * @ 
@@ ** @ 
0 0

样本输出

0 
1 
2 
2

算法

#include<stdio.h>
#include<iostream>
#include<string.h>
#include <queue>
#include<math.h>
using namespace std;
int dir[8][2]={1,0,-1,0,0,1,0,-1,1,1,-1,-1,1,-1,-1,1};
char map[101][101]; 
struct Point{
	int x,y;
} a,b;
int h,l;
void bfs(int x,int y){
	queue<Point> q;
	a.x=x;
	a.y=y;
	q.push(a);
	map[x][y]='*';
	while(!q.empty())
	{
		a=q.front();
		q.pop();
		for(int i=0;i<8;i++)
		{
			b.x=a.x+dir[i][0];
			b.y=a.y+dir[i][1];
			if(b.x>=0&&b.x<h&&b.y>=0&&b.y<l&&map[b.x][b.y]=='@')
			{
				map[b.x][b.y]='*';
				q.push(b);
			} 
		}		
	} 
}
int main()
{
	//freopen("input.txt", "r", stdin);
	while(cin>>h>>l&&h&&l)
	{
	int sum=0;
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<l;j++)
			{
				cin>>map[i][j];	
			}
		}
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<l;j++)
			{
				if(map[i][j]=='@')
				{
				bfs(i,j);
				sum++;
				}				
			}
		}
		cout<<sum<<endl;
	}
    return 0; 
}