gdcpc E 黑白大陆

好久没码，最短路都写错，，，突然想起厕所战神杯写的的floyd，，，，，

希望下下个星期不会逝世。。

#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
#include <queue>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out1.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ", x)
#define pn1(x) printf("Case %d:\n", x)
#define pr2(x) printf("Case #%d: ", x)
#define pn2(x) printf("Case #%d:\n", x)
#define lowbit(x) (x & (-x))

#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;


int n, m, a[51][51], dis[51 * 51], dp[51][51], fa[51 * 51],cor[51*51];
vector<pair<int, int>> v;
pair<int, int> dir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<int> g[51 * 51];
bitset<51 * 51> vis;

int fnd(int x)
{
    return fa[x] == x ? x : fa[x] = fnd(fa[x]);
}

int dj(int k)
{
    int ans = -1, ck = 0;
    if (fnd(k) != k)
        return 0x3f3f3f3f;
    vis.reset();
    memset(dis, 0x3f, sizeof(dis));

    dis[k] = 0;
    priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    q.push({0, k});
    while (!q.empty())
    {
        auto [aa, bb] = q.top();
        q.pop();
        if (vis[bb])
            continue;
        vis[bb] = 1;
        if(cor[k]&&cor[bb])ans=max(ans,aa+1);
        else ans=max(ans,aa);
        for (auto it : g[bb])
        {
            if (aa + 1 < dis[it])
            {
                dis[it] = aa + 1;
                q.push({dis[it], it});
            }
        }
    }
    return ans;
}

int main()
{
    //IN;OUT;
    memset(dis, 0x3f, sizeof(dis));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            fa[i * m + j - m] = i * m + j - m;
            scanf("%d", &a[i][j]);
            cor[i * m + j - m]=a[i][j];
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            for (auto [aa, bb] : dir)
            {
                aa += i, bb += j;
                if (aa && bb && aa <= n && bb <= m)
                {
                    int oa = fnd(aa * m + bb - m), ob = fnd(i * m + j - m);
                    if (a[aa][bb] == a[i][j])
                    {
                        fa[ob] = oa;
                    }
                    else
                        v.push_back({oa, ob});
                }
            }
        }
    }

    for (auto [aa, bb] : v)
    {
        int oa = fnd(aa), ob = fnd(bb);
        g[oa].push_back(ob);
        g[ob].push_back(oa);
    }

    int res = 0x3f3f3f3f;
    for (int i = 1; i <= n * m; ++i)
    {
        res = min(res, dj(i));
    }

    printf("%d\n", res);
}