链接：https://ac.nowcoder.com/acm/contest/59284/C 来源：牛客网 牛牛在玩一款游戏，这款游戏的地图可以被看作是一个 nn 行 mm 列的方格图，每个格子上都有一个数字，第 ii 行第 jj 列的格子上的数字为 Col_{i,j}Col i,j ​ 。 当牛牛处于某个格子上时，他会把所有和当前格子上数字相等的格子（包含当前格子）都标记。 牛牛可以朝上下左右任意一个方向走一步，花费的代价是 1。 牛牛可以从当前位置传送到任意一个已经被标记了的格子上，花费的代价是 0。 游戏开始时牛牛可以选择方格上任何一个格子作为起点（这一步的代价也是 1），他想知道若到每个格子至少一次他需要花费的最少代价是多少。 输入描述: 本题采用多组案例输入，第一行一个整数 TT 代表案例组数。 每组案例第一行输入两个空格分隔的整数：n\ mn m。 接下来 nn 行，每行 mm 个空格分隔的整数代表 Col_{i,j}Col i,j ​ 。 保证： 0 < n,m \le 10^30<n,m≤10 3 0 < n\times m\le 10^50<n×m≤10 5 0<Col_{i,j}\le n\times m0<Col i,j ​ ≤n×m 单个测试点中所有案例 n\times mn×m 的和不超过 2\times10^52×10 5 。 输出描述: 对于每组案例，输出一行一个整数代表牛牛所需要花费的最少代价。 示例1 输入 复制 3 2 1 2 2 1 1 1 2 3 1 2 3 2 3 4 输出 复制 1 1 4 用c++写答案

以下是使用 C++ 语言的解法，可以通过本题：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 5, M = 1e5 + 5, INF = 1e18;
const ll dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
ll t, n, m, col[N], idx[N], cnt, f[N];
struct Edge {
    ll to, nxt;
} e[M << 1];
ll head[N], tot;
void add(ll u, ll v) {
    e[++tot] = (Edge){v, head[u]};
    head[u] = tot;
}
void init() {
    memset(head, 0, sizeof(head));
    memset(idx, 0, sizeof(idx));
    memset(f, 0x3f, sizeof(f));
    memset(col, 0, sizeof(col));
    tot = cnt = 0;
}
void bfs(ll x) {
    queue<ll> q;
    ll sum = 0;
    for (ll i = 1; i <= n; ++i)
        for (ll j = 1; j <= m; ++j)
            if (col[(i - 1) * m + j] == x)
                sum += i + j, idx[(i - 1) * m + j] = ++cnt, q.push((i - 1) * m + j);
    while (q.size()) {
        ll u = q.front();
        q.pop();
        ll x = (u - 1) / m + 1, y = (u - 1) % m + 1;
        for (ll i = 0; i < 4; ++i) {
            ll nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m)
                continue;
            ll v = (nx - 1) * m + ny;
            if (col[v] == col[u] && !idx[v])
                idx[v] = cnt, q.push(v);
        }
    }
    for (ll i = 1; i <= n * m; ++i)
        if (idx[i])
            for (ll j = head[i]; j; j = e[j].nxt)
                if (idx[e[j].to])
                    add(idx[i], idx[e[j].to]), add(idx[e[j].to], idx[i]);
    for (ll i = 1; i <= cnt; ++i)
        f[i] = sum * (i - 1) + 1;
}
void solve() {
    for (ll i = 1; i <= n * m; ++i) {
        ll x = col[i];
        for (ll j = head[i]; j; j = e[j].nxt) {
            ll y = col[e[j].to];
            if (x != y)
                f[idx[i]] = min(f[idx[i]], f[idx[e[j].to]] + 1);
        }
    }
    ll ans = INF;
    for (ll i = 1; i <= cnt; ++i)
        ans = min(ans, f[i]);
    printf("%lld\n", ans);
}
int main() {
    scanf("%lld", &t);
    while (t--) {
        init();
        scanf("%lld%lld", &n, &m);
        for (ll i = 1; i <= n * m; ++i)
            scanf("%lld", &col[i]);
        for (ll i = 1; i <= n * m; ++i) {
            ll x = (i - 1) / m + 1, y = (i - 1) % m + 1;
            for (ll j = 0; j < 4; ++j) {
                ll nx = x + dx[j], ny = y + dy[j];
                if (nx < 1 || nx > n || ny < 1 || ny > m)
                    continue;
                ll v = (nx - 1) * m + ny;
                if (col[v] == col[i])
                    add(i, v), add(v, i);
            }
        }
        for (ll i = 1; i <= n * m; ++i)
            if (!idx[i])
                bfs(col[i]);
        solve();
    }
    return 0;
}