BOJ 5925 Cow Beauty Pageant

void solve(){
    int N, M; cin >> N >> M;
    vector<string> S(N);
    rep(i, 0, N) cin >> S[i];

    vector<vector<int>> board(N, vector<int>(M));
    int color = 0;
    rep(i, 0, N) rep(j, 0, M) {
        if(S[i][j] == 'X' && board[i][j] == 0){
            queue<pii> Q;
            Q.push({i, j});
            board[i][j] = ++color;
            while(!Q.empty()){
                auto [cx, cy] = Q.front(); Q.pop();
                rep(d, 0, 4){
                    int nx = cx + dx[d];
                    int ny = cy + dy[d];
                    if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                    if(S[nx][ny] == 'X' && board[nx][ny] == 0){
                        board[nx][ny] = color;
                        Q.push({nx, ny});
                    }
                }
            }
        }
    }

    vector<ll> dists;
    auto getDist = [&](int c1, int c2) -> ll {
        vector<vector<int>> dist(N, vector<int>(M, -1));
        queue<pii> Q;
        rep(i, 0, N) rep(j, 0, M){
            if(board[i][j] == c1){
                dist[i][j] = 0;
                Q.push({i, j});
            }
        }
        while(!Q.empty()){
            auto [cx, cy] = Q.front(); Q.pop();
            rep(d, 0, 4){
                int nx = cx + dx[d];
                int ny = cy + dy[d];
                if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if(board[nx][ny] == c2){
                    return dist[cx][cy];
                }
                if(board[nx][ny] == 0 && dist[nx][ny] == -1){
                    dist[nx][ny] = dist[cx][cy] + 1;
                    Q.push({nx, ny});
                }
            }
        }
        return (ll)1e18;
    };

    rep(i, 1, 4) rep(j, i+1, 4) dists.push_back(getDist(i, j));
    sort(all(dists));

    ll ans = dists[0] + dists[1];

    auto getDist2 = [&](int cx, int cy, int c) -> ll {
        vector<vector<int>> dist(N, vector<int>(M, -1));
        queue<pii> Q;
        dist[cx][cy] = 0;
        Q.push({cx, cy});
        while(!Q.empty()){
            auto [x, y] = Q.front(); Q.pop();
            rep(d, 0, 4){
                int nx = x + dx[d];
                int ny = y + dy[d];
                if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if(board[nx][ny] == c){
                    return dist[x][y];
                }
                if(board[nx][ny] == 0 && dist[nx][ny] == -1){
                    dist[nx][ny] = dist[x][y] + 1;
                    Q.push({nx, ny});
                }
            }
        }
        return (ll)1e18;
    };
    rep(i, 0, N) rep(j, 0, M) if(board[i][j] == 0){
        ans = min(ans, getDist2(i, j, 1) + getDist2(i, j, 2) + getDist2(i, j, 3) + 1);
    }

    cout << ans << "\n";
}