首页 > 代码库 > cogs 1647. 油田[uva572]
cogs 1647. 油田[uva572]
1647. 油田[uva572]
★ ★ ★ ★ ★ 输入文件：oild.in 输出文件：oild.out 简单对比
时间限制：3 s
内存限制：256 MB
【题目描述】
有一家石油公司负责探勘察某块地底下的石油含量，这块地是矩形的，并且做了勘查的方便被切割成许多小块。然后使用仪器对每一个小块去勘查。包含有石油的小块称为一个pocket。假如两个pocket相连，那么这两个pocket属于同一个oil deposit。（所谓相连的定义与踩地雷游戏中的定义相同，请参考sample input，sample output）
你的任务就是要找出来这块地包含几个不同的oil deposit。
【输入格式】
输入包含好几组资料，每组资料的第一行有2个整数m，n。m代表这块土地的列数，n代表这块地的行数。（1 < =m，n < =100），接下来的m行就是这块地探勘查的内容。‘@‘代表这是一块含石油，‘*‘ 代表这一块不含石油。m= 0 n = 0代表输入结束。
【输出格式】
对每个组测试资料输出oil deposit的数目。
【样例输入】
1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0
【样例输出】
0 1 2 2
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int N=110; const int xd[]={0,-1,-1,-1,0,1,1,1}; const int yd[]={-1,-1,0,1,1,1,0,-1}; bool a[N][N]; int answer,n=1,m=1; char c; struct node{ int x,y; }now,top,nxt; queue<node>q; inline int read() { int x=0;char c=getchar(); while(c<‘0‘||c>‘9‘)c=getchar(); while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar(); return x; } inline void bfs(int x,int y) { now.x=x; now.y=y; q.push(now); while(!q.empty()) { top=q.front(); q.pop(); for(int i=0;i<8;i++) { int xx=top.x+xd[i]; int yy=top.y+yd[i]; if(a[xx][yy]) a[xx][yy]=0, nxt.x=xx, nxt.y=yy, q.push(nxt); } } } int main() { freopen("oild.in","r",stdin); freopen("oild.out","w",stdout); while(1) { answer=0; n=read(); m=read(); if(!n&&!m)return 0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>c; if(c==‘*‘)a[i][j]=0; else a[i][j]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]) answer++, a[i][j]=0, bfs(i,j); printf("%d\n",answer); } return 0; }
cogs 1647. 油田[uva572]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。