首页 > 代码库 > UVA-572-搜索基础题

UVA-572-搜索基础题

2024-09-22 03:03:14   215人阅读

题意

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

样例输出
0
1
2
2

BUNOJ,AC时间:60ms

#include<iostream>#include <stdio.h>#include <memory.h>#include<queue>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<Dir> 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<Dir> 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<<total<<endl;	}	return 0;}

　　

 

UVA-572-搜索基础题


联系
我们