📝 题目大意

给定一个 $N \times M$ 的网格，其中 S 为起点，T 为终点，# 为原有障碍。 你可以放置无限个额外障碍以及至多 $K$ 个炮塔。 胖头鱼星人会从 S 到 T 选择一条受伤害最小的路径前进。如果途中遇到障碍或炮塔，则不能经过该格子。 炮塔会攻击其周围的 8 个方向（即 8 连通相邻格子）。每当星人走到炮塔的攻击范围内，就会受到 1 点伤害。 你的任务是合理布置障碍和炮塔，在保证至少存在一条从 S 到 T 的路径的前提下，使得星人到达目的地所受的最小伤害最大化。

💡 解题思路

1. 核心转化： 既然我们可以放置无限个障碍，那么为了让星人受到的伤害最大，最暴力的策略就是用障碍把其他所有的路都堵死，只留下唯一的一条从 S 到 T 的路径。 因为路只有一条，星人没得选，只能走我们为他铺好的这条路。因此，原问题等价转化为：在网格中寻找一条从 S 到 T 的简单路径，并放置至多 $K$ 个炮塔（炮塔和路径不可重合，均需避开原有障碍 #），使得该路径受到的总伤害最大化。 而路径受到的总伤害，实质上就是所有 8 连通相邻的（路径格子, 炮塔）对的数量。

2. 状态压缩 DP（轮廓线 / 插头 DP）： 题目保证 $\min(N, M) \le 6$，非常适合基于轮廓线的插头 DP。当 $N < M$ 时，我们可以直接将网格转置，从而始终保证轮廓线宽度不超过 6。 逐行逐列扫描网格时，当前格子 $(i, j)$ 可以设定为以下三种类型（cur_type）：

   • 0：障碍（不可通行区域）。
   • 1：路径（星人走的简单路径，S 和 T 处必须为 1）。
   • 2：炮塔（防御塔，总数限制为 $K$）。

3. 状态设计（32 位整数完美压缩）： 要保证只有一条合法路径并计算 8 连通伤害，处理格子 $(i, j)$ 时需要记录：

   • P（插头状态）：长度为 $m+1$，每个元素表示轮廓线上的插头情况。取值为 0（无插头）、1（左括号）、2（右括号）、3（已连通起点 S 或终点 T 的端点独立插头）。占用 $7 \times 2 = 14$ 个 bit。
   • B（方块类型状态）：长度为 $m+1$。取值为 0, 1, 2，记录当前轮廓线上已填好的格子类型，专用于判断 8 连通。占用 $7 \times 2 = 14$ 个 bit。
   • stc（已放炮塔数）：最高 15，占用 4 个 bit。 总共只需要 $14+14+4 = 32$ bit，刚好打包进一个 uint32_t。

4. 伤害计算与 B 数组的妙用： 当轮廓线推到 $(i, j)$ 时，B 数组精确地保留了左、左上、上、右上四个邻居的历史选择结果：

   • 若 $(i, j)$ 填 1（路径），只要它的四个邻居中有 2（炮塔），每个 2 都会产生 1 点伤害。
   • 若 $(i, j)$ 填 2（炮塔），只要它的四个邻居中有 1（路径），每个 1 都会产生 1 点伤害。 因为我们是从左到右、从上到下遍历，这种“只往后看一半方向”的检查可以刚好不重不漏地覆盖全部的 8 连通对！

5. 插头连通性转移：

   • 端点格 (S 或 T)：必须填 1，且消耗或生成端点。若新生成则设为插头 3；若吸收已有的 1 或 2，则通过括号匹配逻辑将其对应的另一端转化为插头 3。
   • 普通格填 1：应用标准插头 DP 的转移规律。如果是两个 3 插头相遇，则表示完成了整条从 S 到 T 的连接！
   • 填 0 或 2：该处不能有插头，因此要求上方和左侧均无插头流入。

⏱️ 复杂度分析

• 时间复杂度：$O(N \times M \times |States|)$，其中 $|States|$ 是任意单步中的合法状态数量。因为网格非常窄且连通性限制严格，绝大部分无效状态会被剪枝，$|States|$ 最大仅在数千左右。整体耗时极低（通常十几毫秒跑完）。
• 空间复杂度：由于采用滚动哈希表，只需维护两层的状态，大小均设为 $\approx 10^6$，空间消耗约为几 MB，属于 $O(|States|)$ 级别，非常充裕。

💻 标准代码 (C++)

#include <cstdint>
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

const int MOD = 500009;
struct HashMap {
    int head[MOD];
    int nxt[1000000];
    uint32_t key[1000000];
    int val[1000000];
    int size;

    void init() {
        memset(head, -1, sizeof(head));
        size = 0;
    }
    
    void clear() {
        for (int i = 0; i < size; ++i) {
            head[key[i] % MOD] = -1;
        }
        size = 0;
    }

    void insert(uint32_t k, int v) {
        int h = k % MOD;
        for (int i = head[h]; i != -1; i = nxt[i]) {
            if (key[i] == k) {
                if (v > val[i]) val[i] = v;
                return;
            }
        }
        key[size] = k;
        val[size] = v;
        nxt[size] = head[h];
        head[h] = size++;
    }
} HM[2];

int n, m, K;
char grid[25][25];

inline void decode(uint32_t state, int* P) {
    for (int i = 0; i <= m; ++i) P[i] = (state >> (i * 2)) & 3;
}

inline uint32_t encode(int* P) {
    uint32_t state = 0;
    for (int i = 0; i <= m; ++i) state |= (P[i] << (i * 2));
    return state;
}

int find_match_1(int* P, int pos) {
    int tot = 1;
    for (int i = pos - 1; i >= 0; --i) {
        if (P[i] == 2) tot++;
        else if (P[i] == 1) tot--;
        if (tot == 0) return i;
    }
    return -1;
}

int find_match_2(int* P, int pos) {
    int tot = 1;
    for (int i = pos + 1; i <= m; ++i) {
        if (P[i] == 1) tot++;
        else if (P[i] == 2) tot--;
        if (tot == 0) return i;
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> m >> K)) return 0;

    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    // 保证轮廓线宽度不超过 6
    if (n < m) {
        char tmp[25][25];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                tmp[j][i] = grid[i][j];
        swap(n, m);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                grid[i][j] = tmp[i][j];
            }
        }
    }

    HM[0].init();
    HM[1].init();

    int now = 0;
    HM[now].insert(0, 0);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            HM[now ^ 1].clear();
            for (int idx = 0; idx < HM[now].size; ++idx) {
                uint32_t k = HM[now].key[idx];
                int v = HM[now].val[idx];

                int P[8], B[8];
                decode(k & 0x3FFF, P);
                decode((k >> 14) & 0x3FFF, B);
                int stc = k >> 28;

                int p1 = P[j], p2 = P[j + 1];
                int c_left = (j == 0) ? 0 : B[j - 1];
                int c_tl = (j == 0) ? 0 : B[j];
                int c_top = B[j + 1];
                int c_tr = (j == m - 1) ? 0 : B[j + 2];

                auto push_state = [&](int* nP, int* nB, int n_stc, int damage) {
                    if (j == m - 1 && nP[m] != 0) return;
                    if (i == n - 1 && nP[j] != 0) return;
                    uint32_t nk = encode(nP) | (encode(nB) << 14) | (n_stc << 28);
                    HM[now ^ 1].insert(nk, v + damage);
                };

                for (int cur_type = 0; cur_type <= 2; ++cur_type) {
                    if (grid[i][j] == '#' && cur_type != 0) continue;
                    if ((grid[i][j] == 'S' || grid[i][j] == 'T') && cur_type != 1) continue;
                    if (cur_type == 2 && stc >= K) continue;

                    int damage = 0;
                    if (cur_type == 1) damage = (c_left == 2) + (c_tl == 2) + (c_top == 2) + (c_tr == 2);
                    else if (cur_type == 2) damage = (c_left == 1) + (c_tl == 1) + (c_top == 1) + (c_tr == 1);

                    int nP[8], nB[8];
                    memcpy(nP, P, sizeof(nP));
                    memcpy(nB, B, sizeof(nB));
                    nB[j] = cur_type;
                    int n_stc = stc + (cur_type == 2 ? 1 : 0);

                    if (cur_type != 1) {
                        if (p1 == 0 && p2 == 0) {
                            nP[j] = 0; nP[j + 1] = 0;
                            push_state(nP, nB, n_stc, damage);
                        }
                    } else {
                        if (grid[i][j] == 'S' || grid[i][j] == 'T') {
                            if (p1 == 0 && p2 == 0) {
                                nP[j] = 0; nP[j + 1] = 3; push_state(nP, nB, n_stc, damage);
                                nP[j] = 3; nP[j + 1] = 0; push_state(nP, nB, n_stc, damage);
                            } else if (p1 != 0 && p2 == 0) {
                                nP[j] = 0; nP[j + 1] = 0;
                                if (p1 == 1) nP[find_match_2(P, j)] = 3;
                                else if (p1 == 2) nP[find_match_1(P, j)] = 3;
                                push_state(nP, nB, n_stc, damage);
                            } else if (p1 == 0 && p2 != 0) {
                                nP[j] = 0; nP[j + 1] = 0;
                                if (p2 == 1) nP[find_match_2(P, j + 1)] = 3;
                                else if (p2 == 2) nP[find_match_1(P, j + 1)] = 3;
                                push_state(nP, nB, n_stc, damage);
                            }
                        } else {
                            if (p1 == 0 && p2 == 0) {
                                nP[j] = 1; nP[j + 1] = 2; push_state(nP, nB, n_stc, damage);
                            } else if (p1 == 0 && p2 != 0) {
                                nP[j] = 0; nP[j + 1] = p2; push_state(nP, nB, n_stc, damage);
                                nP[j] = p2; nP[j + 1] = 0; push_state(nP, nB, n_stc, damage);
                            } else if (p1 != 0 && p2 == 0) {
                                nP[j] = 0; nP[j + 1] = p1; push_state(nP, nB, n_stc, damage);
                                nP[j] = p1; nP[j + 1] = 0; push_state(nP, nB, n_stc, damage);
                            } else if (p1 == 1 && p2 == 1) {
                                nP[j] = 0; nP[j + 1] = 0; nP[find_match_2(P, j + 1)] = 1;
                                push_state(nP, nB, n_stc, damage);
                            } else if (p1 == 2 && p2 == 2) {
                                nP[j] = 0; nP[j + 1] = 0; nP[find_match_1(P, j)] = 2;
                                push_state(nP, nB, n_stc, damage);
                            } else if (p1 == 2 && p2 == 1) {
                                nP[j] = 0; nP[j + 1] = 0; push_state(nP, nB, n_stc, damage);
                            } else if (p1 == 3 && p2 == 1) {
                                nP[j] = 0; nP[j + 1] = 0; nP[find_match_2(P, j + 1)] = 3;
                                push_state(nP, nB, n_stc, damage);
                            } else if (p1 == 1 && p2 == 3) {
                                nP[j] = 0; nP[j + 1] = 0; nP[find_match_2(P, j)] = 3;
                                push_state(nP, nB, n_stc, damage);
                            } else if (p1 == 3 && p2 == 2) {
                                nP[j] = 0; nP[j + 1] = 0; nP[find_match_1(P, j + 1)] = 3;
                                push_state(nP, nB, n_stc, damage);
                            } else if (p1 == 2 && p2 == 3) {
                                nP[j] = 0; nP[j + 1] = 0; nP[find_match_1(P, j)] = 3;
                                push_state(nP, nB, n_stc, damage);
                            } else if (p1 == 3 && p2 == 3) {
                                nP[j] = 0; nP[j + 1] = 0; push_state(nP, nB, n_stc, damage);
                            }
                        }
                    }
                }
            }
            now ^= 1;
        }

        HM[now ^ 1].clear();
        for (int idx = 0; idx < HM[now].size; ++idx) {
            uint32_t k = HM[now].key[idx];
            int v = HM[now].val[idx];
            int P[8], B[8];
            decode(k & 0x3FFF, P);
            decode((k >> 14) & 0x3FFF, B);
            int stc = k >> 28;

            for (int ki = m; ki >= 1; --ki) P[ki] = P[ki - 1]; P[0] = 0;
            for (int ki = m; ki >= 1; --ki) B[ki] = B[ki - 1]; B[0] = 0;

            uint32_t nk = encode(P) | (encode(B) << 14) | (stc << 28);
            HM[now ^ 1].insert(nk, v);
        }
        now ^= 1;
    }

    int ans = 0;
    for (int i = 0; i < HM[now].size; ++i) {
        if ((HM[now].key[i] & 0x3FFF) == 0) {
            ans = max(ans, HM[now].val[i]);
        }
    }
    cout << ans << "\n";
    return 0;
}