当前位置 博文首页 > u012938183的博客：油田(zoj 1709, poj 1562)
【题目描述】
GeoSurvComp 地质探测公司负责探测地下油田。 每次 GeoSurvComp 公
司都是在一块长方形的土地上来探测油田。 在探测时， 他们把这块土地用
网格分成若干个小方块， 然后逐个分析每块土地， 用探测设备探测地下是
否有油田。 方块土地底下有油田则称为 pocket， 如果两个pocket相邻， 则
认为是同一块油田， 油田可能覆盖多个 pocket。
你的工作是计算长方形的土地上有多少个不同的油田。
【输入描述】
输入文件中包含多个测试数据， 每个测试数据描述了一个网格。
每个网格数据的第一行为两个整数： m n， 分别表示网格的行和列； 如
果m = 0， 则表示输入结束， 否则 1≤m≤100， 1 ≤n≤100。
接下来有m 行数据， 每行数据有 n 个字符（不包括行结束符） 。 每个字
符代表一个小方块， 如果为"*"， 则代表没有石油， 如果为"@"， 则代表
有石油， 是一个 pocket。
【输出描述】
对输入文件中的每个网格， 输出网格中不同的油田数目。 如果两块不同
的 pocket 在水平、 垂直、 或者对角线方向上相邻， 则被认为属于同一块油
田。 每块油田所包含的 pocket 数目不会超过 100。
// dfs深搜
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m;
bool vis[110][110];
char mp[110][110];
const int dx[8]={-1,1,0,0,-1,1,-1,1};
const int dy[8]={0,0,-1,1,-1,1,1,-1};
void dfs(int x, int y)
{
vis[x][y] = true;
for(int i = 0; i < 8; i ++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx <= 0 || nx > n || ny <= 0 || ny > m)
{
continue;
}
if(vis[nx][ny])
{
continue;
}
if(mp[nx][ny] != '@')
{
continue;
}
dfs(nx, ny);
}
}
int main()
{
while(scanf("%d%d", &n, &m) == 2){
if(m == 0 && n == 0)
{
break;
}
memset(vis, false, sizeof vis);
for(int i= 1; i <= n; i ++)
{
scanf("%s", mp[i] + 1);
}
int cnt = 0;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
if(! vis[i][j] && mp[i][j] == '@')
{
dfs(i, j);
cnt ++;
}
}
}
printf("%d\n", cnt);
}
return 0;
}
