题目连接：https://vjudge.net/problem/HDU-1241node
题意：问有几个油田，一个油田由相邻的‘@’，组成。ios
思路：bfs，dfs均可以，只须要遍历地图，遇到‘@’，跑一遍搜索，标记跑过的点，而后油田数+1.spa
1 #include <iostream> 2 #include <cstring> 3 #include<vector> 4 #include<string> 5 #include <cmath> 6 #include <map> 7 #include <queue> 8 #include <algorithm> 9 using namespace std; 10 11 #define inf (1LL << 31) - 1 12 #define rep(i,j,k) for(int i = (j); i <= (k); i++) 13 #define rep__(i,j,k) for(int i = (j); i < (k); i++) 14 #define per(i,j,k) for(int i = (j); i >= (k); i--) 15 #define per__(i,j,k) for(int i = (j); i > (k); i--) 16 17 const int N = 110; 18 int mv[8][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }, 19 { 1, 1 }, { -1, -1 }, { -1, 1 }, { 1, -1 } }; 20 char mp[N][N]; 21 bool vis[N][N]; 22 int n, m; 23 24 struct node{ 25 int x, y; 26 }; 27 28 inline void init(){ 29 rep(i, 1, n) rep(j, 1, m) vis[i][j] = false; 30 } 31 32 inline void input(){ 33 34 init(); 35 rep(i, 1, n) rep(j, 1, m) cin >> mp[i][j]; 36 } 37 38 inline bool check(int x, int y){ 39 return x >= 1 && x <= n && y >= 1 && y <= m; 40 } 41 42 void bfs(int now_x, int now_y){ 43 44 vis[now_x][now_y] = true; 45 46 queue<node> que; 47 que.push(node{ now_x, now_y }); 48 49 while (!que.empty()){ 50 51 node tmp = que.front(); 52 que.pop(); 53 54 rep__(p, 0, 8){ 55 int dx = tmp.x + mv[p][0]; 56 int dy = tmp.y + mv[p][1]; 57 58 if (check(dx, dy) && !vis[dx][dy] && mp[dx][dy] == '@'){ 59 vis[dx][dy] = true; 60 que.push(node{ dx, dy }); 61 } 62 } 63 } 64 } 65 66 void work(){ 67 68 int ans = 0; 69 70 rep(i, 1, n) rep(j, 1, m){ 71 //附加条件，这个‘@’没被访问过，说明是新的油田的一部分 72 if (mp[i][j] == '@' && !vis[i][j]){ 73 bfs(i, j); 74 ++ans; 75 } 76 } 77 78 cout << ans << endl; 79 } 80 81 int main(){ 82 83 ios::sync_with_stdio(false); 84 cin.tie(0); 85 86 while (cin >> n >> m){ 87 88 if (m == 0) break; 89 90 input(); 91 work(); 92 } 93 94 return 0; 95 }