题意：给一个图，求连通块的个数。（题中是一某点周围8个点均为连通区域）
思路： 这道题就是一道很基础的搜索染色（计数），我一开始用的bfs但是一直MLE，所以就使用消耗空间更少的dfs
完整代码：
#include <iostream> #include <cstring> #include <cmath> #include <queue> #include <stack> using namespace std; const int maxn = 101; int n,m; char map[maxn][maxn]; int vis[maxn][maxn]; int mov[][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{-1,1},{1,-1}}; struct node{ int x,y; }; void dfs(node s) { if(map[s.x][s.y]=='#'||vis[s.x][s.y]!=0||s.x<1||s.y<1||s.x>n||s.y>m)//不满足条件就返回 return; vis[s.x][s.y]=1;//染色 for(int i=0; i<8; i++)//判断往哪走 { node t; t.x=s.x+mov[i][0]; t.y=s.y+mov[i][1]; if(map[t.x][t.y]=='@'&&vis[t.x][t.y]==0&&t.x>0&&t.x<=n&&t.y>0&&t.y<=m) { dfs(t); } } } //void bfs(node s){ //bfs中queue开的空间太大 // queue<node>Q; // Q.push(s); // while(Q.size()){ // node t = Q.front(); // vis[t.x][t.y] =1;//访问 // Q.pop(); // for(int i=0;i<8;i++){ // node nex; // nex.x =t.x+ mov[i][0]; // nex.y =t.y+ mov[i][1]; // if(nex.x<1||nex.y<1||nex.x>n||nex.y>m) continue;//边界条件 // else if(vis[nex.x][nex.y]||(map[nex.x][nex.y]=='*')) continue; // else{ // Q.push(nex); // } // } // } //} int getblocks(){ int cnt = 0; for(int i =1;i<=n;i++) for(int j=1;j<=m;j++){ if(!vis[i][j]&&(map[i][j]=='@')) { cnt++; node s; s.x = i,s.y = j; dfs(s); } } return cnt; } int main(){ while(cin>>n>>m){ char ch; memset(vis,0,sizeof(vis)); if(n==0&&m==0) break; for(int i =1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>ch; map[i][j] = ch; } int ans = getblocks(); cout<<ans<<endl; } }