HDU1241 Oil Deposits

题目:

小烤 同志负责探测lz地下石油储藏。 小烤现在在一块矩形区域探测石油。他们通过专业设备,来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻(横向相邻,纵向相邻,还有对角相邻),那么他们被认为是同一油藏的一部分。在这块矩形区域,可能有很多油藏。你的任务是确定有多少不同的油藏。

输入:

输入可能有多个矩形区域(即可能有多组测试)。每个矩形区域的起始行包含m和n,表示行和列的数量,1<=n,m<=100,如果m =0表示输入的结束,接下来是n行,每行m个字符。每个字符对应一个小方格,并且要么是'*',代表没有油,要么是'@',表示有油。(注意多组数据,必要的数组要及时清空~)

输出:

对于每一个矩形区域,输出油藏的数量。两个小方格是相邻的,当且仅当他们水平或者垂直或者对角线相邻(即8个方向)。

样例:

HDU1241 Oil Deposits

分析:逐行列寻找@,若找到执行DFS把与此@相连的@(包括此@)全部置为*

 1 #include<iostream>
 2 #include<sstream>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<string>
 6 #include<cstring>
 7 #include<algorithm>
 8 #include<functional>
 9 #include<iomanip>
10 #include<numeric>
11 #include<cmath>
12 #include<queue>
13 #include<vector>
14 #include<set>
15 #include<cctype>
16 #define PI acos(-1.0)
17 const int INF = 0x3f3f3f3f;
18 const int NINF = -INF - 1;
19 typedef long long ll;
20 using namespace std;
21 int m, n;
22 char maze[105][105];
23 int dx[8] = {1, 0, 1, -1, -1, 0, 1, -1}, dy[8] = {0, 1, 1, -1, 0, -1, -1, 1};
24 void dfs(int x, int y)
25 {
26     for (int i = 0; i < 8; ++i)
27     {
28         int nx = x + dx[i], ny = y + dy[i];
29         if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == '@')
30         {
31             maze[nx][ny] = '*';
32             dfs(nx, ny);
33         }
34     }
35 }
36 int main()
37 {
38     while (cin >> m >> n)
39     {
40         if (m == 0 && n == 0) break;
41         int ans = 0;
42         for (int i = 0; i < m; ++i)
43         {
44             for (int j = 0; j < n; ++j)
45                 cin >> maze[i][j];
46         }
47         for (int i = 0; i < m; ++i)
48         {
49             for (int j = 0; j < n; ++j)
50             {
51                 if (maze[i][j] == '@')
52                 {
53                     maze[i][j] = '*';
54                     dfs(i, j);
55                     ans++;
56                 }
57             }
58         }
59         cout << ans << endl;
60     }
61     return  0;
62 }

 

上一篇:UVA572 Oil Deposits DFS求解


下一篇:题目--oil Deposits(油田) 基础DFS(深度搜索)