Untitled

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};

int R, C, houseCnt;
char board[55][55];
int compId[55][55];
int distHouse[16][16];
int tempDist[55][55];

struct Node {
    int x, y, cost;
};

void dfs_mark(int x, int y, int id) {
    compId[x][y] = id;
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (board[nx][ny] == 'X' && compId[nx][ny] == -1) {
            dfs_mark(nx, ny, id);
        }
    }
}

void find_components() {
    memset(compId, -1, sizeof(compId));
    houseCnt = 0;

    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (board[i][j] == 'X' && compId[i][j] == -1) {
                dfs_mark(i, j, houseCnt);
                houseCnt++;
            }
        }
    }
}

void bfs_distance() {
    memset(distHouse, 0x3f, sizeof(distHouse));

    for (int id = 0; id < houseCnt; id++) {
        queue<Node> q;

        memset(tempDist, 0x3f, sizeof(tempDist));
        
        int sx = -1, sy = -1;
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                if (compId[i][j] == id) {
                    sx = i; sy = j;
                    break;
                }
            }
            if (sx != -1) break;
        }

        q.push({sx, sy, 0});
        tempDist[sx][sy] = 0;

        while (!q.empty()) {
            auto [x, y, cost] = q.front(); q.pop();

            if (compId[x][y] != -1) {
                int other = compId[x][y];
                distHouse[id][other] = min(distHouse[id][other], cost);
            }

            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];

                if (board[nx][ny] == 'X') {
                    if (cost < tempDist[nx][ny]) {
                        tempDist[nx][ny] = cost;
                        q.push({nx, ny, cost});
                    }
                }
                else if (board[nx][ny] == 'S') {
                    if (cost + 1 < tempDist[nx][ny]) {
                        tempDist[nx][ny] = cost + 1;
                        q.push({nx, ny, cost + 1});
                    }
                }
            }
        }
    }
}

int solve_tsp() {
    int maxMask = 1 << houseCnt;
    vector<vector<int>> dp(houseCnt, vector<int>(maxMask, INF));

    for (int i = 0; i < houseCnt; i++) {
        dp[i][1 << i] = 0;
    }

    for (int mask = 1; mask < maxMask; mask++) {
        for (int u = 0; u < houseCnt; u++) {
            if (dp[u][mask] == INF) continue;

            for (int v = 0; v < houseCnt; v++) {
                int newMask = mask | (1 << v);
                dp[v][newMask] = min(dp[v][newMask], dp[u][mask] + distHouse[u][v]);
            }
        }
    }

    int res = INF;
    for (int i = 0; i < houseCnt; i++) {
        res = min(res, dp[i][maxMask - 1]);
    }

    return (res >= INF ? -1 : res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(board, '.', sizeof(board));

    cin >> R >> C;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> board[i][j];
        }
    }

    find_components();
    bfs_distance();

    cout << solve_tsp() << '\n';
    return 0;
}