admin 管理员组

文章数量: 1086866

油田(zoj 1709, poj 1562)

油田(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;
}

本文标签： 油田(zoj 1709 poj 1562)

版权声明：本文标题：油田(zoj 1709, poj 1562) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1693764316a241467.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。