题意
GeoSurvComp 地理调查公司负责发现石油存储,这次GeoSurvComp公司在一个大型矩形区域上工作,
它用一个网格分割地表,然后用可感知装备来单独分析每块小方格区域下是否包含石油,有油的地块叫做pocket,如果俩个相邻的pocket,那么它们是相同石油存储的一部分,石油存储能够非常大,可能会包含多个pocket,你的任务是计算出在一个方格中有多少不同的石油存储.输入
输入文件里包含一个或多个方格,每个方格由一行包含m,n俩个数字开头,m是方格的行,n是列.如果m=0代表输入结束,要不然1 ≤ m ≤ 100,1 ≤ n ≤ 100随后m行,每行有n个字符,每个字符代表一块地,*代表没有石油,@代表一个石油pocket输出
对于每个网格,输出不同的石油存储,俩个水平相邻,垂直相邻,对角线相邻的不同pocket是相同石油存储的一部分,一个石油存储不会包含超过100pockets样例输入
1 1*3 5*@*@***@***@*@*1 8@@****@*5 5****@*@@*@*@**@@@@*@@@**@0 0样例输出
0122BUNOJ,AC时间:60ms
#include#include #include #include using namespace std;#define MAXR 100#define MAXC 100struct Dir{ int r; int c;} dir[8] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, 1 }, { 0, -1 }, { 1, 1 }, { 1, 0 }, { 1, -1 } };void bfs(queue q, char map[][100],int used[][100], int r, int c){ while (!q.empty()) { Dir d = q.front(); q.pop(); for(int i = 0; i < 8; i++) { int nr = d.r + dir[i].r; int nc = d.c + dir[i].c; if(nr < 0 || nc < 0 || nr == r || nc == c||used[nr][nc]==1|| map[nr][nc] == '*' ) { continue; } used[nr][nc]=1; Dir dd; dd.r=nr; dd.c=nc; q.push(dd); } }}int main(){ int r, c; while (cin >> r >> c) { if(r==0&&c==0) return 0; char map[MAXR][MAXC]; int used[MAXR][MAXC]; memset(used, 0, sizeof(used)); memset(map, '*', sizeof(map)); for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) { cin >> map[i][j]; } int total = 0; queue q; Dir d; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) { if(used[i][j] == 0&&map[i][j]=='@') { total++; used[i][j]=1; d.r=i; d.c=j; q.push(d); bfs( q, map, used, r, c); } } cout< <
posted on 2017-05-14 16:29 阅读( ...) 评论( ...)