数据
题目大意： 已经很简洁了
题解：
把原图中相同颜色且相邻的点缩成一个点
若在原图中，两个不同颜色的联通块有边重合
代表可以花费1的代价使得两个联通块颜色一样
枚举第一个操作的点，则在新图中以它为起点的最长路径就是当前答案
注意，如果终点是黑点，答案要加1
$$O((n*m)^2)$$
AC代码
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
const int N=75,inf=1e9;
int n,m,cnt,tot,ans;
int last[N*N],id[N][N],f[N*N],dis[N*N];
bool mp[N*N][N*N];
char ch[N][N];
struct edge{
int to,next;
}e[(N*N)<<2];
void add_edge(int u,int v){
e[++cnt]=(edge){v,last[u]};last[u]=cnt;
e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
void dfs(int x,int y,int tot){
id[x][y]=tot;
for(int k=0;k<4;k++){
int nx=x+dx[k],ny=y+dy[k];
if(1<=nx && nx<=n && 1<=ny && ny<=m && !id[nx][ny] && ch[nx][ny]==ch[x][y])
dfs(nx,ny,tot);
}
}
void bfs(int x){
for(int i=1;i<=tot;i++)dis[i]=inf;
queue<int> q;q.push(x);dis[x]=0;
int res=f[x];
while(!q.empty()){
int u=q.front();q.pop();
for(int i=last[u];i;i=e[i].next){
int v=e[i].to;
if(dis[v]==inf){
dis[v]=dis[u]+1;
q.push(v);
res=max(res,dis[v]+f[v]);
}
}
}
ans=min(ans,res);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",ch[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!id[i][j]){
dfs(i,j,++tot);
f[tot]=(ch[i][j]=='B');
}
for(int x=1;x<=n;x++)
for(int y=1;y<=m;y++)
for(int k=0;k<4;k++){
int nx=x+dx[k],ny=y+dy[k];
if(1<=nx && nx<=n && 1<=ny && ny<=m)
if(id[x][y]!=id[nx][ny] && !mp[id[x][y]][id[nx][ny]]){
add_edge(id[x][y],id[nx][ny]);
mp[id[x][y]][id[nx][ny]]=1;
mp[id[nx][ny]][id[x][y]]=1;
}
}
ans=inf;
for(int i=1;i<=tot;i++)
bfs(i);
printf("%d
",ans);
return 0;
}
作者：skl_win
出处：https://www.cnblogs.com/shaokele/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。