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种,如图:
算法设计如下:
判断是否出界,是否已有连通分量号或不是@’;
对字符矩阵中每个位置进行判断，如果未标记连通分量号且是’@’，则从该位置深度优先搜索;
搜索时将该位置标记连通分量号为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; }
