7 ЛКШ

//  #define pragma

#ifdef pragma
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif // pragma

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define all(x) begin(x), end(x)
#define pb push_back
#define x first
#define y second
#define int long long
#define zero(two) memset(two, 0, sizeof(two))

using namespace std;
using namespace __gnu_pbds;


typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef long double ld;
typedef vector<vi> matrix;
template<typename T>
using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ld PI = atan2(0, -1);

void seriy() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    cout << fixed << setprecision(10);
    #if 1
        freopen("input", "r", stdin);
        freopen("output", "w", stdout);
    #endif
}

const int MAXN = 50 + 10;
const int INF = 1e15 + 7;
const int MAXLOG = 31;
const int MOD = 998244353;
const int BASE = 47;

struct node {
    int x, y, cnt, isl;
};

struct edge {
    int u, v, w;
};

bool used2[MAXN][MAXN];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
char c[MAXN][MAXN];
int n, m, ans = 0;
int d[MAXN][MAXN];
int cur = 0;
vb kek(MAXN);
vector<pii> st;
vector<vector<pii>> g;
vi pr(MAXN), sz(MAXN);
vector<pii> ed(MAXN);

int get(int a) {
    if(a == pr[a]) return a;
    return pr[a] = get(pr[pr[a]]);
}

void unite(int a, int b) {
    int pa = a, pb = b;
    a = get(a);
    b = get(b);
    if(a != b) {
        if(sz[a] < sz[b]) {
            swap(a, b);
        }
        if(ed[a].x == pa && ed[b].x == pb) {
            ed[a].x = ed[a].y;
            ed[a].y = ed[b].y;
        }
        else if(ed[a].y == pa && ed[b].x == pb) {
            ed[a].x = ed[a].x;
            ed[a].y = ed[b].y;
        }
        else if(ed[a].x == pa && ed[b].y == pb) {
            ed[a].x = ed[a].y;
            ed[a].y = ed[b].x;
        }
        else {
            ed[a].x = ed[a].x;
            ed[a].y = ed[b].x;
        }
        pr[b] = a;
        sz[a] += sz[b];
    }
}

void dfs(int x, int y) {
    used2[x][y] = 1;
    for(int k = 0; k < 4; k++) {
        int tox = x + dx[k];
        int toy = y + dy[k];
        if(tox >= 0 && tox < n && toy >= 0 && toy < m && !used2[tox][toy] && c[tox][toy] == 'X') {
            dfs(tox, toy);
        }
    }
}


bool cmp(edge a, edge b) {
    return a.w < b.w;
}

signed main() {
    seriy();
    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> c[i][j];
        }
    }
    int cnt = 0;
    map<pii, int> mp;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(!used2[i][j] && c[i][j] == 'X') {
                st.pb({i, j});
                dfs(i, j);
                cnt++;
                mp[{i, j}] = cnt;
            }
        }
    }
    // cerr << 1;
    fill(&d[0][0], &d[0][0] + MAXN * MAXN, INF);
    for(int i = 0; i < st.size(); i++) {
        pr[i] = i;
        ed[i] = {i, i};
        // cerr << i << '\n';
        deque<node> q;
        // cerr << st[i].x << " " << st[i].y << "    ";
        q.push_back({st[i].x, st[i].y, 0, 1});
        bool used[n][m];
        zero(used);
        used[st[i].x][st[i].y] = 1;
        while(!q.empty()) {
            node u = q.front();
            q.pop_front();
            if(mp[{u.x, u.y}]) {
                // cerr << u.x << " " << u.y << " " << u.cnt << "  ";
                // cerr << i << " " << mp[{u.x, u.y}] - 1 << " " << u.cnt << '\n';
                d[i][mp[{u.x, u.y}] - 1] = min(d[i][mp[{u.x, u.y}] - 1], u.cnt);
                // if(i != mp[{u.x, u.y}] - 1) continue;
            }
            for(int k = 0; k < 4; k++) {
                int tox = u.x + dx[k];
                int toy = u.y + dy[k];
                if(tox >= 0 && tox < n && toy >= 0 && toy < m && !used[tox][toy] && c[tox][toy] != '.') {
                    used[tox][toy] = 1;
                    if(c[tox][toy] == 'S') {
                        q.push_back({tox, toy, u.cnt + 1, u.isl});
                    }
                    else {
                        int isl = u.isl;
                        if(c[u.x][u.y] == 'S' && c[tox][toy] == 'X') {
                            isl = u.isl + 1;
                        }
                        q.push_front({tox, toy, u.cnt, isl});
                    }
                }
            }
        }
        // cerr << '\n';
    }
    // cerr << 1;
    g.resize(st.size());
    vector<edge> edges;
    // cerr << '\n';
    for(int i = 0; i < st.size(); i++) {
        for(int j = 0; j < st.size(); j++) {
            // cerr << d[i][j] << " ";
            if(i == j || d[i][j] == INF) continue;
            // edges.pb({i, j, d[i][j]});
            g[i].pb({j, d[i][j]});
            // cerr << i << " " << j << " " << d[i][j] << '\n';
        }
        // cerr << '\n';
    }
    int dp[(1ll << 17)][st.size()];
    for(int i = 0; i < (1ll << 17); i++) {
        for(int j = 0; j < st.size(); j++) {
            dp[i][j] = INF;
            if((i ^ (1ll << j)) == 0) dp[i][j] = 0;
        }
    }
    for(int i = 0; i < (1ll << 17); i++) {
        for(int j = 0; j < st.size(); j++) {
            if(((1ll << j) & i) && (i & (i - 1)) > 0) {
                for(auto k : g[j]) {
                    dp[i][j] = min(dp[i][j], dp[(i ^ (1ll << j))][k.x] + d[k.x][j]);
                }
            }
        }
    }
    int ans = INF;
    for(int i = 0; i < st.size(); i++) {
        ans = min(ans, dp[(1ll << (st.size())) - 1][i]);
    }
    cout << ans;
    return 0;
}