L-FarmIrrigation（并查集

#include 
#include 
#include <string>
#include 
#include 

using namespace std;

int pre[500000];
int node[500000];
const int u[50 ]={1,1,0,0,1,0,1,1,0,1,1};
const int l [50 ]={1,0,1,0,0,1,1,1,1,0,1};
const int r [50 ]={0,1,0,1,0,1,1,0,1,1,1};
const int d[50 ]={0,0,1,1,1,0,0,1,1,1,1};

void init( int n){
     for( int i=0 ;i<=n;i++)
        pre[i] = i;
}

int find( int x){

     int r= x;
     while( pre[x] != x){
        x= pre[x];
     }
     int t;
     while( r!=x){
        t = pre[r];
        pre[r] = x;
        r = t;
     }
     return x;
}

void add( int a ,int b){
   // cout<
    int x=find(a);
    int y=find(b);
    if( x!=y) pre[x] =y;
    return ;
}

int main( ){
     int m ,n;
     while( cin>>m>>n){
            if( m<0 || n<0) break;
         int an = m*n;
         init( an);
         string op;
         int cnt = 1;
         for( int i=1 ;i<=m ;i++){
            cin>> op;
            for( int j=0 ; j)
                node[cnt++] =(int)(op[j]-'A');
         }

         for( int i=1 ;i<=an ;i++){
             int t=node[i];
             int ut=i - n ,lt=i -1 ,rt=i+1 ,dt=i+n;
             if( u[ t] && ut>0 && d[ node[ut] ])add(i ,ut);
             if( l[ t] && i%n !=1 && n !=1 && r[ node[lt] ])add(i ,lt); //就是这一行
             if( r[ t] && i%n !=0  && n !=1&& l[ node[rt] ])add(i ,rt);
             if( d[ t] && dt<=an && u[ node[dt] ])add(i ,dt);
         }
         int ans=0;
         for( int i=1 ; i<=an ;i++){
            if( pre[i] == i)ans++;
          //  cout<
         }
         printf("%d\n" ,ans);
     }
     return 0;
}