主题思想 ： 这个题目就是求有多少个联通分量。用union set结构很容易做到
union set 核心代码，带优化版本
int a[maxn]; int cnt[maxn]; // 优化使用的，用来计数，一个根下有多少个节点。 // init for(int i=0;i<maxn;i++){ a[i]=i; cnt[i]=1; } int find(int v){ if(a[v]!=v) a[v]=Find(a[v]); return a[v]; } void union(int v,int w){ int p=find(v); int q=find(w); if(p！=q){ //数量少的作为根。 if(cnt[p]>cnt[q]){ a[p]=a[q]; cnt[q]+=cnt[p]; }else{ a[q]=a[p]; cnt[p]+=cnt[q]; } } }此外就是构图过程，创建图的过程，不用考虑4个方向，逐行逐列遍历，只需要右边，和下边两个方向就可以。
AC代码
#include <iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> using namespace std; const int maxn=2510; char g[55][55]; int dir[4][2]={0,1,0,-1,1,0,-1,0};// r,l,d,u int a[maxn]; int cnt[maxn]; int n,m; struct Type{ char c; int left=0; int right=0; int top=0; int down=0; Type(){} Type(char c):c(c){ switch(c){ case 'A': left=1; top=1; break; case 'B': right=1; top=1; break; case 'C': left=1; down=1; break; case 'D': right=1; down=1; break; case 'E': top=1; down=1; break; case 'F': left=1; right=1; break; case 'G': left=1; right=1; top=1; break; case 'H': top=1; left=1; down=1; break; case 'I': left=1; right=1; down=1; break; case 'J': top=1; down=1; right=1; break; case 'K': top=1; down=1; left=1; right=1; break; } } }; Type node[55][55]; int Find(int v){ if(v==a[v]) return a[v]; else return Find(a[v]); } void UN(int p,int q){ int r,s; r=Find(p); s=Find(q); if(r!=s){ //union q,p by union the root of p or the root of q if(cnt[r]<cnt[s]){ a[r]=a[s]; // cnt[s]+=cnt[r]; }else{ a[s]=a[r]; cnt[r]+=cnt[s]; } } } int main() { string s; while(scanf("%d%d",&m,&n)!=EOF){ if(m<0&&n<0) break; for(int i=0;i<m;i++){ cin>>s; for(int j=0;j<n;j++){ g[i][j]=s[j]; //init the union find int t=i*n+j; a[t]=t; cnt[t]=1; node[i][j]=Type(s[j]); } } //build the map for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ int xx,yy; //we just need charge two direction the right and the down //right xx=i; yy=j+1; if(yy<n) { if(node[i][j].right==1&&node[xx][yy].left==1) UN(i*n+j,xx*n+yy); } // down xx=i+1; yy=j; if(xx<m){ if(node[i][j].down==1&&node[xx][yy].top==1) UN(i*n+j,xx*n+yy); } } } // int ans=0; for(int i=0;i<m*n;i++){ if(a[i]==i) ans++; } printf("%d\n",ans); } return 0; }