记录编号	598043	评测结果	AAAAAA
题目名称	原神一统计划	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.518 s
提交时间	2024-12-26 21:00:36	内存使用	83.72 MiB

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

int n, m, vis[110][110], nm[110][110], cnt = 0, d[20][20], f[20][1 << 20], ans, u[20], dp[20][55][55];

// 深度优先搜索，标记每个岛屿
void dfs(int x, int y, int k) {
    if (nm[x][y] <= 0 || x < 1 || y < 1 || x > n || y > m || vis[x][y] == 1)
        return;
    nm[x][y] = k;
    vis[x][y] = 1;
    dfs(x + 1, y, k);
    dfs(x, y + 1, k);
    dfs(x - 1, y, k);
    dfs(x, y - 1, k);
}

// 计算岛屿间的最短游泳路径
void get(int x, int y, int k, int s) {
    if (nm[x][y] < 0 || x < 1 || y < 1 || x > n || y > m)
        return;
    if (dp[k][x][y] >= 0) {
        if (s >= dp[k][x][y])
            return;
    }
    dp[k][x][y] = s;
    if (nm[x][y] > 0 && nm[x][y] != k) {
        d[k][nm[x][y]] = min(d[k][nm[x][y]], s);
        if (u[nm[x][y]] == 0) {
            k = nm[x][y];
            dp[k][x][y] = 0;
            u[k] = 1;
            s = 0;
        }
        else
            return;
    }
    if (nm[x][y] == 0) {
        s++;
    }
    get(x + 1, y, k, s);
    get(x, y + 1, k, s);
    get(x - 1, y, k, s);
    get(x, y - 1, k, s);
}

int main() {
	freopen("nl.in","r",stdin);
	freopen("nl.out","w",stdout); 
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char a;
            cin >> a;
            if (a == 'X') {
                nm[i][j] = 1;
            } else if (a == 'S') {
                nm[i][j] = 0;
            } else {
                nm[i][j] = -1;
            }
        }
    }

    // 标记岛屿
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (nm[i][j] > 0 && vis[i][j] == 0) {
                dfs(i, j, ++cnt);
            }
        }
    }

    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    memset(dp, -1, sizeof(dp));

    // 计算岛屿间的最短游泳路径
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (nm[i][j] == 0 || nm[i][j] == -1)
                continue;
            if (u[nm[i][j]] == 0) {
                u[nm[i][j]] = 1;
                get(i, j, nm[i][j], 0);
            }
        }
    }

    // 使用 Floyd 算法计算最短路径
    for (int k = 1; k <= cnt; k++) {
        for (int i = 1; i <= cnt; i++) {
            for (int j = 1; j <= cnt; j++) {
                if (i != j)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    memset(f, 0x3f, sizeof(f));
    ans = 0x3f3f3f3f;
    for (int i = 1; i <= cnt; i++) {
        f[i][1 << (i - 1)] = 0;
    }

    // 动态规划求解最短游泳路径
    for (int j = 0; j < (1 << cnt); j++) {
        for (int i = 1; i <= cnt; i++) {
            if ((j & (1 << (i - 1))) == 0 || f[i][j] > 1e8)
                continue;
            for (int k = 1; k <= cnt; k++) {
                if ((j & (1 << (k - 1))) != 0)
                    continue;
                f[k][j | (1 << (k - 1))] = min(f[k][j | (1 << (k - 1))], f[i][j] + d[i][k]);
            }
        }
    }

    for (int i = 1; i <= cnt; i++) {
        ans = min(ans, f[i][(1 << cnt) - 1]);
    }
    cout << ans;
    return 0;
}