# Uva 572 - Oil Deposits --- # 題目大意 給定一個n*m,由@和*形成的圖,求@形成的連通塊個數。連通是指上、右上、右、右下、下、左下、左、左上這八個方向的方格相同 --- # 題解 BFS --- ```=c++ #include <bits/stdc++.h> #define ll long long #define pb push_back #define pf push_front #define ft first #define sec second #define pr pair<int,int> #define ISCC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; int t ,n ,m ,ans ,pos ,vis[105][105] ,dir[][2] = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}}; string g[105] ,s; void sol(int x ,int y) { queue<pr> que; que.push({x,y}); vis[x][y] = 1; while(!que.empty()) { pr now = que.front(); que.pop(); vis[now.ft][now.sec] = 1; for(int i=0 ;i<8 ;i++) { int gx = now.ft + dir[i][0] ,gy = now.sec + dir[i][1]; if(gx<1 || gy<1 || gx>n || gy>m) continue; if(g[gx][gy]!='@' || vis[gx][gy]) continue; que.push({gx ,gy}); } } } int main() { ISCC; while(cin >> n >> m && n && m) { ans = 0; memset(vis,0,sizeof(vis)); for(int i=1 ;i<=n ;i++) cin >> s ,g[i] = ' ' + s; for(int i=1 ;i<=n ;i++) for(int j=1 ;j<=m ;j++) if(g[i][j]=='@' && !vis[i][j]) sol(i ,j) ,ans++; cout << ans << '\n'; } return 0; } ```