[bzoj2638] 黑白染色

　　比较蛋疼的是我们可以先染个底色，再在底色上染别的东西。

　　由ccz大爷的题解可得。。将目标状态里相同颜色的联通块缩点后，枚举起点，生成树里的最大节点深度就是需要的次数了，

　　如果最大深度是白色的话记得-1.

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=,xx[]={,-,,},yy[]={,,,-};

 struct zs{

     int too,pre;

 }e[];int tot,last[maxn];

 struct zs1{int x,y;}dl[maxn];

 char mp[][];

 int id[][];

 int col[maxn],d[maxn];

 short dis[maxn];

 bool u[maxn];

 int i,j,k,n,m,ans,cnt;

 int ra;char rx;

 inline int read(){

     rx=getchar(),ra=;

     while(rx<''||rx>'')rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;

 }

 inline void insert(int a,int b){

 //  printf("%d-->%d\n",a,b);

     e[++tot].too=b,e[tot].pre=last[a],last[a]=tot,

     e[++tot].too=a,e[tot].pre=last[b],last[b]=tot;

 }

 int main(){

     n=read(),m=read();

     for(i=;i<=n;i++)scanf("%s",mp[i]+);

     for(i=;i<=n;i++)for(j=;j<=m;j++)if(!id[i][j]){

         int l=,r=,nx,ny,x,y;dl[]=(zs1){i,j};

         cnt++,col[cnt]=mp[i][j]=='B',id[i][j]=cnt;

         while(l<r){

             l++,nx=dl[l].x,ny=dl[l].y;

             for(k=;k<;k++){

                 x=nx+xx[k],y=ny+yy[k];

                 if(x<||y<||x>n||y>m)continue;

                 if(mp[x][y]==mp[i][j]&&!id[x][y])

                     dl[++r]=(zs1){x,y},id[x][y]=cnt;

                 else if(id[x][y])insert(id[x][y],cnt);

             }

         }

     }

     ans=1e9;

     for(i=;i<=cnt;i++){

         memset(dis,,(cnt+)<<);

         int l=,r=,now,j;d[]=i,dis[i]=;

         while(l<r)

             for(j=last[now=d[++l]];j;j=e[j].pre)if(!dis[e[j].too])

                 dis[e[j].too]=dis[now]+,d[++r]=e[j].too;

         ans=min(ans,dis[d[r]]-(!col[d[r]]));

     }

     printf("%d\n",ans);

 }