[ACM_ZJUT_2012]勘探油田
杰拉斯 | 时间:2012-03-28, Wed | 6,352 views编程算法
勘探油田
Time Limit:1000MS Memory Limit:32768K
Description
某石油勘探公司正在按计划勘探地下油田资源。他们工作在一片长方形的地域中,首先将该地域划分为许多小正方形区域,然后使用探测设备分别探测每一块小正方形区域是否有油。若在一块小正方形区域中探测到有油,则标记为’@’,否则标记为’*’。如果两个相邻区域都为1,那么它们同属于一个石油带,一个石油带可能包含很多小正方形区域,而你的任务是要确定在一片长方形地域中有多少个石油带。 所谓相邻,是指两个小正方形区域上下、左右、左上右下或左下右上同为’@’。
Input
输入数据将包含一些长方形地域数据,每个地域数据的第一行有两个正整数m和n,表示该地域为m*n个小正方形所组成,如果m为0,表示所有输入到此结束。否则,后面m(1≤m≤100)行数据,每行有n(1≤n≤100)个字符,每个字符为’@’或’*’,表示有油或无油。每个长方形地域中,’@’的个数不会超过100。
Output
每个长方形地域,输出油带的个数,每个油带值占独立的一行。油带值不会超过100。
Sample Input
1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@**@ *@**@ @@@*@ @@**@ 0 0
Sample Output
0 1 2 2
Source
这道题思路比较清晰,从数组第一位开始遍历,遍历到'@'则将坐标放入队列中,然后取出队头,搜索队头周围的'@',将坐标放入队列中,并将队头出队,且将队头修改为*及@以外的任意字符,直到队列为空,则说明遍历完一个油田,总油田数加一,遍历完数组后输出总油田数。
#include<iostream> #include<queue> using namespace std; struct Pos{ int x; int y; Pos(int _x, int _y):x(_x),y(_y){}; }; int offset[8][2] = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}, {-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int main(){ int m, n, i, j; while(cin >> m >> n){ if(m == 0 && n == 0) break; int num = 0; char **a = new char*[m]; for(i = 0; i < m; ++i){ a[i] = new char[n]; cin >> a[i]; } queue<Pos> q; for(i = 0; i < m; ++i){ for(j = 0; j < n; ++j){ if(a[i][j] == '@'){ q.push(Pos(i, j)); while(!q.empty()){ Pos p = q.front(); a[p.x][p.y] = 'o'; q.pop(); for(int k = 0; k < 8; ++k){ int x = p.x + offset[k][0]; int y = p.y + offset[k][1]; if(x >= 0 && x < m && y >= 0 && y < n && a[x][y] == '@'){ q.push(Pos(x, y)); } } } ++num; } } } cout << num << endl; } return 0; }
如需转载请注明出处:杰拉斯的博客
当前暂无评论 »