黑白染色模板题
首先通过DFS缩点，将所有相同状态的连通块缩成一个点
之后枚举每一个点进行BFS，计算变成最终状态的最小值

#include<bits/stdc++.h>
using namespace std;
const int N = 50, M = 2500;
int T, n, m, cnt, ans;
char s[N];
char g[N][N];
int h[M], e[4 * M], ne[4 * M], idx;
int st[N][N];
bool vis[M];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
struct node {
    int dist, id;
};
int main() {
    scanf("%d", &T);
    while (T -- ) {
        scanf("%d%d", &n, &m);
        memset(st, 0, sizeof st);
        memset(h, -1, sizeof h);
        idx = 0;
        cnt = 1;
        for (int i = 1; i <= n; i ++ ) {
            scanf("%s", s + 1);
            for (int j = 1; j <= m; j ++ )
                g[i][j] = s[j];
        }
        function<void(int, int)> add = [&](int a, int b) {
            e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
        };
        //缩点
        function<void(int, int, int, char)> dfs = [&](int x, int y, int id, char ch) {
            for (int i = 0; i < 4; i ++ ) {
                int tx = x + dx[i];
                int ty = y + dy[i];
                if (tx < 1 || tx > n || ty > m || ty < 1)   continue;
                if (g[tx][ty] == ch) {
                    if (st[tx][ty] == 0) {
                        st[tx][ty] = id;
                        dfs(tx, ty, id, ch);
                    }
                }
                else if (st[tx][ty] != 0) {  //在缩点的同时完成加边操作
                    int temp = st[tx][ty];
                    add(id, temp), add(temp, id);
                }
            }
        };
        for (int i = 1; i <= n; i ++ ) {
            for (int j = 1; j <= m; j ++ ) {
                if (!st[i][j]) {
                    st[i][j] = cnt;
                    dfs(i, j, cnt, g[i][j]);
                    cnt ++;
                }
            }
        }
        ans = 0x3f3f3f3f;
        function<int(int)> bfs = [&](int x) {  //BFS计算每个起点变成最终状态的最小步数
            queue<node> q;
            q.push({0, x});
            int ans = -1;
            memset(vis, 0, sizeof vis);
            vis[x] = true;
            while (q.size()) {
                auto t = q.front();
                q.pop();
                ans = max(t.dist, ans);
                int u = t.id;
                for (int i = h[u]; i != -1; i = ne[i]) {
                    int j = e[i];
                    if (vis[j]) continue;
                    vis[j] = true;
                    q.push({t.dist + 1, j});
                }
            }
            return ans;
        };
        for (int i = 1; i < cnt; i ++ ) 
            ans = min(ans, bfs(i));
        printf("%d\n", ans);
    }
    return 0;
}