UVA572油藏 Oil Deposits

UVA572油藏 Oil Deposits

题目描述

某石油勘探公司正在按计划勘探地下油田资源，工作在一片长方形的地域中。他们首先将该地域划分为许多小正方形区域，然后使用探测设备分别探测每一块小正方形区域内是否有油。
含有油的地块称为油田。如果两个油田相邻，则它们是相同油藏的一部分。油藏可能非常大并且可能包含许多油田。您的工作是确定长方形的地域中包含多少不同的油藏。

输入

文件包含一个或多个网格。每个网格以包含m和n的行开始，n是数字
网格中的行和列，用一个空格隔开。如果m = 0，表示输入结束;
否则，1≤m≤100,1≤n≤100。接下来是m行，每行n个字符(不包括在内)
行尾字符)。“*” 代表没有油， “@”:表示油藏。

输出

对于每个网格，输出不同的石油储量的数量。两个不同的油藏是同一个油田的一部分,水平、垂直或对角线上相邻的油田。石油矿床将包含不超过100多个油藏。

输入样例

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

输出样例

0
1
2
2

思路分析

1.本题主要考察DFS.
如图所示:@表示油田,*代表没有油,主要统计油藏的块数,也就是图中连通分量的个数.

每个位置访问的方向有8种,如图:

算法设计如下:

1. 判断是否出界,是否已有连通分量号或不是@’;
2. 对字符矩阵中每个位置进行判断，如果未标记连通分量号且是’@’，则从该位置深度优先搜索;
3. 搜索时将该位置标记连通分量号为id,从该位置出发,沿八个方向继续深度优先搜索。。

特别注意:因为有可能包含多个连通分支，因此需要从每个未标记的’@'深搜。

参考代码

#include<iostream>
#include<string>
#include<string.h>
using namespace std; 
const int maxn = 105;
int m, n,cnt;
int setid[maxn][maxn];//标记矩阵
string arr[maxn];//存储字符的矩阵

void def(int x,int y,int id)
{
   
	if (x < 0 || x >= m || y < 0 || y >= n)//判断是否越界
		return;
	if (setid[x][y] > 0 || arr[x][y] != '@')//已有连通分量号或不是@
		return;
	setid[x][y] = id;//做标记2
	for (int i = -1; i <= 1; i++)//八个方向进行深搜.
	{
   
		for (int j = -1; j <= 1; j++)
		{
   
			if (i  || j )//两者不能都为0
			{
   
				def(x + i, y + j, id);
			}
		}
	}
}

int main()
{
   
	while (cin >> m >> n && m && n)
	{
   
		cnt = 0;
		memset(setid, 0, sizeof(setid));//初始化
		for (int i = 0; i < m; i++)
		{
   
			cin >> arr[i];
		}
		for (int i = 0; i < m; i++)//防止遗漏,一个一个再次判断
		{
   
			for (int j = 0; j < n; j++)
			{
   
				if (arr[i][j] == '@' && setid[i][j] == 0)
				{
   
					def(i, j, ++cnt);
				}
			}
		}
		cout << cnt << endl;
	}
	return 0;
}