問題描述
因為前面選手們的幫忙，小蛤智商提升了！他現在在玩一個神奇的遊戲:給出了一個n*m的棋盤，其中的格子有的黑，有的白。我們對一個格子進行操作，可以使這個格子與它所處的顔色相同的聯通塊中的所有格子顔色全部取反。問至少要多少次操作可以使所有格子變白？
輸入格式
第一行兩個整數n，m代表棋盤尺寸；
接下n行一個字元串描述每一行棋盤情況：W為白B為黑。
輸出格式
輸出一個整數表示最少的次數。
樣例輸入
樣例輸出
資料範圍
思路：首先去除聯通塊的影響來看題，就是縮點(友善思考,最後寫的時候不用縮點)。那麼新圖就單純地變成了一個黑白相間的塊。
現在考慮對于兩個點，我要讓這兩個點處于同一個連通塊中的最小代價是什麼。那麼此時兩個點顔色不同，那麼必然要用代價為1.也就是矩陣上建圖，不同色之間連代價為1的邊.
B-(1)-W-(1)--B
那麼使得任意兩點在同一連通塊中的最小操作次數就是這兩點之間的最短路徑。
u為起點,v為終點。跑以u為起點的最短路之後,dis[v]就意味着将u變成v色，也就是和v同色的連通塊的最小代價。
比如我現在左1B為起點。dis[1]=1;（本身黑色，題目要求白色)
dis[2]=1(将1号變成白色聯通的最小代價是1)
dis[3]=2(由于B是黑色，再+1。B先變成2号W色，再由W色變成3号B色。最後由于3号B是黑色，需要最後轉化成白色，在這種情況下使得所有點最終變成白色塊的答案是3）
接着枚舉2号點，3号點跑最短路。
這麼了解可能有一點怪。但是要想到:
我枚舉每一個點作為起點,然後dis[v]表示這個點作為起點，和v變成同一個顔色塊的最短距離。此時我預設，将V作為最終态。如果黑色就+1，然而這個點可能不是最終态，那就會由其他的v的路徑來更新。
雖然不知道哪個點是最終态，但是我們能保證最終态一定是本次起點中花費最大的那個點的距離。和v一樣，可以保證最大值一定是全局一樣。
是以最短路的最大值，必定是全都一樣。最後讓最大值取最小的那個。
至于代碼上的一個輸入,我由于scanf("%c")，wa了一早上和一晚上。這是個以前碰到的問題，之前cin克服了。但是卡cin了。太久沒碰了，要用scanf("%s")每次讀一行。
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5;
typedef int LL;
inline LL read(){LL x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
typedef pair<LL,LL>P;
struct edge{
LL to,cost;
};
vector<edge>g[5000];
LL dis[5000];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool vis[5000];
char str[110][110];
LL n,m;
LL dijkstra(LL st){
LL ans=-1;
LL s=st;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
priority_queue< P, vector<P> , greater<P> >que;
que.push({0,s});
while(!que.empty()){
P now=que.top();que.pop();
LL u=now.second;
if(vis[u]) continue;
vis[u]=true;
for(LL i=0;i<g[u].size();i++){
edge e=g[u][i];
LL v=e.to;LL fee=e.cost;
if(dis[v]>dis[u]+fee){
dis[v]=dis[u]+fee;
que.push({dis[v],v});
}
}
}
for(LL i=1;i<=n;i++){
for(LL j=1;j<=m;j++){
ans=max(ans,dis[(i-1)*m+j]+(str[i][j]=='B'));
}
}
return ans;
}
int main(void)
{
/// freopen("5.in","r",stdin);
/// freopen("mysolve.out","w",stdout);
n=read();m=read();
for(LL i=1;i<=n;i++){
scanf("%s",str[i]+1);
}
if(n==1&&m==1){
if(str[1][1]=='B') printf("1\n");
else printf("0\n");
return 0;
}
for(LL i=1;i<=n;i++){
for(LL j=1;j<=m;j++){
for(LL k=0;k<4;k++){
LL xx=i+dx[k];LL yy=j+dy[k];
if(xx<1||xx>n||yy<1||yy>m) continue;
g[(i-1)*m+j].push_back({(xx-1)*m+yy,(str[i][j]==str[xx][yy]?0:1)});
g[(xx-1)*m+yy].push_back({(i-1)*m+j,(str[i][j]==str[xx][yy]?0:1)});
}
}
}
/*
for(LL i=1;i<=n*m;i++){
for(auto j:g[i]){
cout<<j.to<<" "<<j.cost<<" ";
}
cout<<"\n";
}*/
LL sum=0x3f3f3f3f;
for(LL i=1;i<=n*m;i++){
LL t=dijkstra(i);
sum=min(sum,t);
}
printf("%d\n",sum);
return 0;
}