题解

将地图逐格扫描时的限制（必须保持 $S$ 与 $T$ 连通、炮塔数不超过 $K$）与代价统计揉到一起，最合适的工具是插头 DP。状态按行推进：对前若干行已经处理好的前缀，只关心当前行及其上一行的轮廓情况即可。

具体地，给每一列额外保留一个“插头”，用 4 bit 编码表示该列上端的连通块编号以及该列是否已经放置炮塔、是否被障碍封死、是否已经被炮塔覆盖。b1[i] 表示第 $i$ 列插头所属的连通块编号，b2[i] 表示这一列的格子当前的类型（空地、障碍、炮塔以及是否会对通过者造成伤害），整行的轮廓编码由哈希表保存。每转移一格，枚举：放置障碍、放置炮塔或留空通行，并相应更新插头信息以及累计“如果以后路径经过这里会受到的伤害”。当一格被声明为炮塔时，会同时在 8 个方向上标记受到炮塔攻击的格子；放置障碍则直接在插头中切断这条通路；留空格需要维护连通块的合并与拆分，使得地图最终仅保留一条从 $S$ 到 $T$ 的通路。

状态中还附带“已经放置的炮塔数量”，因此总的 DP 维度是 f[row parity][used turrets][state id]，使用滚动数组和哈希桶维护。枚举完所有格子之后，在恰好使用不超过 $K$ 个炮塔的所有状态里取最大值，即可得到在满足连通性的前提下喵星人必经路径上能造成的最大总伤害。

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

const int N = 21, M = 8, C = 16;
int n, m, c, a[N][M];
const int TOT = 2e5 + 5, P = 1e5 + 5;
int f[2][C][TOT], ans;
int b1[M], b2[M];
bool o; int g, cnt_lj3;

struct HXB {
	struct node {int s, nxt;} e[TOT];
	int tot, head[P];
	
	void clr() {
		tot = 0;
		memset(head, 0, sizeof(head));
		return;
	}
	
	int operator [] (int s) {
		int x = s % P;
		for (int i = head[x]; i; i = e[i].nxt) {
			if (e[i].s == s) {
				return i;
			}
		}
		e[++tot] = {s, head[x]}, head[x] = tot;
		return tot;
	}
	
	void roll() {
		for (int i = 1; i <= tot; i++) {
			e[i].s &= (1 << (m << 2)) - 1;
			e[i].s <<= 4;
		}
		return;
	}
} H[2][C];

void cal_b(int s) {
	for (int i = 1; i <= m + 1; i++) {
		int x = s & 15;
		b1[i] = (x >= 2) + (x >= 6) + (x >= 10);
		while (x >= 6) {
			x -= 4;
		}
		b2[i] = x;
		s >>= 4;
	}
	return;
}

int cal_s() {
	int s = 0, dy[4], dy_cnt = 0;
	dy[0] = 0, dy[1] = dy[2] = dy[3] = -1;
	for (int i = m + 1; i; i--) {
		if (dy[b1[i]] == -1) {
			dy[b1[i]] = ++dy_cnt;
		}
		int x = dy[b1[i]] ? b2[i] + 4 * (dy[b1[i]] - 1) : b2[i];
		s = s << 4 | x;
	}
	return s;
}

bool hvr(int b) {
	return b == 4 || b == 5;
}

bool hvd(int b) {
	return b == 3 || b == 5;
}

void upd(int x, int y, int i, int b1y, int b2y, int sh) {
	if (x == n && hvd(b2y) || y == m && hvr(b2y) || cnt_lj3 + (b2y > 1) == 4) {
		return;
	}
	b1[y] = b1y, b2[y] = b2y;
	int s = cal_s();
	f[o][i][H[o][i][s]] = max(f[o][i][H[o][i][s]], g + sh);
	return;
}

void print() {
	cout << "b1: ";
	for (int i = 1; i <= m + 1; i++) {
		cout << b1[i] << " ";
	}
	cout << "\n";
	cout << "b2: ";
	for (int i = 1; i <= m + 1; i++) {
		cout << b2[i] << " ";
	}
	cout << "\n";
	cout << "f: " << g << "\n\n";
	return;
}

void dp() {
	f[0][0][H[0][0][0]] = 0;
	o = 1;
	for (int x = 1; x <= n; x++) {
		for (int y = 1; y <= m; y++, o ^= 1) {
			for (int i = 0; i <= c; i++) {
				memset(f[o][i] + 1, 0, H[o][i].tot << 2);
				H[o][i].clr();
			}
			for (int i = 0; i <= c; i++) {
				for (int j = 1; j <= H[!o][i].tot; j++) {
					g = f[!o][i][j];
					int s = H[!o][i].e[j].s;
					cal_b(s);
					int t1 = b2[y - 1], t2 = b2[y], t3 = b2[y + 1], t4 = y != m ? b2[y + 2] : 0;
					cnt_lj3 = (t1 > 1) + (t2 > 1) + (t3 > 1);
					int cnt_lj = cnt_lj3 + (t4 > 1);
					int cnt_pt = (t1 == 1) + (t2 == 1) + (t3 == 1) + (t4 == 1);
					bool lt = hvr(t1), up = hvd(t3);
//					cout << x << " " << y << " " << i << "\n";
//					print();
					if (a[x][y] == 1) {
						if (!lt && !up) {
							upd(x, y, i, 0, 0, 0);
						}
					}
					else if (a[x][y] == 2) {
						if (lt && !up && t3 < 2) {
							upd(x, y, i, b1[y - 1], 2, cnt_pt);
						}
						else if (!lt && up && t1 < 2) {
							upd(x, y, i, b1[y + 1], 2, cnt_pt);
						}
						else if (!lt && !up && t1 < 2 && t3 < 2) {
							upd(x, y, i, 3, 3, cnt_pt);
							upd(x, y, i, 3, 4, cnt_pt);
						}
					}
					else if (lt && up) {
						if (b1[y - 1] != b1[y + 1]) {
							int b1y = b1[y - 1];
							for (int k = 1; k <= m + 1; k++) {
								if (b1[k] == b1y) {
									b1[k] = b1[y + 1];
								}
							}
							upd(x, y, i, b1[y + 1], 2, cnt_pt);
						}
					}
					else if (lt && !up) {
						if (t3 < 2) {
							upd(x, y, i, b1[y - 1], 3, cnt_pt);
							upd(x, y, i, b1[y - 1], 4, cnt_pt);
						}
					}
					else if (!lt && up) {
						if (t1 < 2) {
							upd(x, y, i, b1[y + 1], 3, cnt_pt);
							upd(x, y, i, b1[y + 1], 4, cnt_pt);
						}
					}
					else {
						if (t1 < 2 && t3 < 2) {
							upd(x, y, i, 3, 5, cnt_pt);
						}
						upd(x, y, i, 0, 0, 0);
						if (i != c) {
							upd(x, y, i + 1, 0, 1, cnt_lj);
						}
					}
				}
			}
		}
		for (int i = 0; i <= c; i++) {
			H[!o][i].roll();
		}
	}
	for (int i = 0; i <= c; i++) {
		for (int j = 0; j <= H[!o][i].tot; j++) {
			ans = max(ans, f[!o][i][j]);
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> c;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int x = i, y = j;
			if (n < m) {
				x = j, y = i;
			}
			char ch; cin >> ch;
			if (ch == '#') {
				a[x][y] = 1;
			}
			else if (ch == 'S' || ch == 'T') {
				a[x][y] = 2;
			}
		}
	}
	if (n < m) {
		swap(n, m);
	}
	dp();
	cout << ans;
	return 0;
}
/*
直接记录格子的状态。
无需管联通情况，因为只要只在 s 和 t 单方向开始就一定是一条路径。
搜索状态数后空间还是大，只有开 vector。

假了。
由于要求一条路径，所以要维护联通情况避免回路。
只会用到路径是否有向右和向下的延申，状态可以简化一些。
*/