题目:
小烤 同志负责探测lz地下石油储藏。 小烤现在在一块矩形区域探测石油。他们通过专业设备,来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻(横向相邻,纵向相邻,还有对角相邻),那么他们被认为是同一油藏的一部分。在这块矩形区域,可能有很多油藏。你的任务是确定有多少不同的油藏。
输入:
输入可能有多个矩形区域(即可能有多组测试)。每个矩形区域的起始行包含m和n,表示行和列的数量,1<=n,m<=100,如果m =0表示输入的结束,接下来是n行,每行m个字符。每个字符对应一个小方格,并且要么是'*',代表没有油,要么是'@',表示有油。(注意多组数据,必要的数组要及时清空~)
输出:
对于每一个矩形区域,输出油藏的数量。两个小方格是相邻的,当且仅当他们水平或者垂直或者对角线相邻(即8个方向)。
样例:
分析:逐行列寻找@,若找到执行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 }