[BZOJ2638]黑白染色

题目大意：

你有一个\(n\times m(n,m\le50)\)的矩形，一开始所有格子都是白色，然后给出一个目标状态的矩形，有的地方是白色，有的地方是黑色，你每次可以选择一个同色四连通块进行反转。问最少操作次数。

思路：

类似ZOJ3781。将所有同色四连通块缩点，枚举起点，求最远点的距离最小值（如果终点是黑点则还需+1）。

源代码：

#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
#include<algorithm>
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
inline bool check(const char &ch) {
    return ch=='B'||ch=='W';
}
inline int getval() {
    register char ch;
    while(!check(ch=getchar()));
    return ch=='B';
}
const int N=51,TOT=2501;
const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
int n,m,tot,bel[N][N],dis[TOT];
bool map[N][N],w[TOT][TOT],vis[TOT],col[TOT];
std::vector<int> e[TOT];
inline void add_edge(const int &u,const int &v) {
    e[u].push_back(v);
    e[v].push_back(u);
}
inline bool check(const int &x,const int &y) {
    return 1<=x&&x<=n&&1<=y&&y<=m;
}
void dfs(const int &x,const int &y) {
    bel[x][y]=tot;
    for(register int i=0;i<4;i++) {
        const int nx=x+dx[i],ny=y+dy[i];
        if(!check(nx,ny)||bel[nx][ny]) continue;
        if(map[nx][ny]==col[tot]) dfs(nx,ny);
    }
}
std::queue<int> q;
inline int bfs(const int &s) {
    std::fill(&dis[1],&dis[tot]+1,0);
    std::fill(&vis[1],&vis[tot]+1,false);
    q.push(s);
    vis[s]=true;
    int ret=0;
    while(!q.empty()) {
        const int &x=q.front();
        ret=std::max(ret,dis[x]+col[x]);
        for(register unsigned i=0;i<e[x].size();i++) {
            const int &y=e[x][i];
            if(!vis[y]) {
                dis[y]=dis[x]+1;
                q.push(y);
                vis[y]=true;
            }
        }
        q.pop();
    }
    return ret;
}
int main() {
    n=getint(),m=getint();
    for(register int x=1;x<=n;x++) {
        for(register int y=1;y<=m;y++) {
            map[x][y]=getval();
        }
    }
    for(register int x=1;x<=n;x++) {
        for(register int y=1;y<=m;y++) {
            if(!bel[x][y]) {
                col[++tot]=map[x][y];
                dfs(x,y);
            }
        }
    }
    for(register int x=1;x<=n;x++) {
        for(register int y=1;y<=m;y++) {
            const int u=bel[x][y];
            for(register int i=0;i<4;i++) {
                const int nx=x+dx[i],ny=y+dy[i];
                if(!check(nx,ny)) continue;
                const int v=bel[nx][ny];
                if(u!=v) {
                    w[u][v]=w[v][u]=true;
                }
            }
        }
    }
    for(register int i=1;i<=tot;i++) {
        for(register int j=1;j<i;j++) {
            if(w[i][j]) add_edge(i,j);
        }
    }
    int ans=INT_MAX;
    for(register int i=1;i<=tot;i++) {
        ans=std::min(ans,bfs(i));
    }
    printf("%d\n",ans);
    return 0;
}

[BZOJ2638]黑白染色

原文：https://www.cnblogs.com/skylee03/p/9802945.html