RT。一份 BFS 代码：

#include <bits/stdc++.h>

using namespace std;

namespace liuzimingc {
const int N = 105;
const int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };

int n, m, dfn[N], low[N];
int sx, sy, ex, ey, sx_p, sy_p;
bool vis[N][N][N][N];
char s[N][N];
struct node {
	int sx, sy, sx_p, sy_p, step;
};
deque<node> q;

void bfs() {
	vis[sx][sy][sx_p][sy_p] = true;
	q.emplace_back((node){ sx, sy, sx_p, sy_p, 0 });
	while (q.size()) {
		node now = q.front(); q.pop_front();
		for (int i = 0; i < 4; i++) {
			int x = now.sx_p + dx[i], y = now.sy_p + dy[i];
			if (x < 1 || x > n || y < 1 || y > m || s[x][y] == 'S') continue;
			if (x == now.sx && y == now.sy) {
				int nx = x + dx[i], ny = y + dy[i];
				if (nx < 1 || nx > n || ny < 1 || ny > m || s[nx][ny] == 'S') continue;
				if (vis[nx][ny][x][y]) continue;
				vis[nx][ny][x][y] = true;
				q.emplace_back((node){ nx, ny, x, y, now.step + 1 });
				if (nx == ex && ny == ey) {
					cout << now.step + 1 << endl;
					return;
				}
			}
			else {
				if (vis[now.sx][now.sy][x][y]) continue;
				vis[now.sx][now.sy][x][y] = true;
				q.emplace_front((node){ now.sx, now.sy, x, y, now.step });
			}
		}
	}
	cout << "NO" << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> (s[i] + 1);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (s[i][j] == 'M') sx_p = i, sy_p = j;
			else if (s[i][j] == 'P') sx = i, sy = j;
			else if (s[i][j] == 'K') ex = i, ey = j;
	bfs();
	return 0;
}
} // namespace liuzimingc

int main() {
	liuzimingc::main();
	return 0;
}

稳定 TLE。但是仅将 struct 换成 <tuple> 就可以直接 AC：

#include <bits/stdc++.h>

using namespace std;

namespace liuzimingc {
const int N = 105;
const int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
#define tii tuple<int, int, int, int, int>

int n, m, dfn[N], low[N];
int sx, sy, ex, ey, sx_p, sy_p;
bool vis[N][N][N][N];
char s[N][N];
deque<tii> q;

void bfs() {
	vis[sx][sy][sx_p][sy_p] = true;
	q.emplace_back(make_tuple(sx, sy, sx_p, sy_p, 0));
	while (q.size()) {
		tii now = q.front(); q.pop_front();
		for (int i = 0; i < 4; i++) {
			int x = get<2>(now) + dx[i], y = get<3>(now) + dy[i];
			if (x < 1 || x > n || y < 1 || y > m || s[x][y] == 'S') continue;
			if (x == get<0>(now) && y == get<1>(now)) {
				int nx = x + dx[i], ny = y + dy[i];
				if (nx < 1 || nx > n || ny < 1 || ny > m || s[nx][ny] == 'S') continue;
				if (vis[nx][ny][x][y]) continue;
				vis[nx][ny][x][y] = true;
				q.emplace_back(make_tuple(nx, ny, x, y, get<4>(now) + 1));
				if (nx == ex && ny == ey) {
					cout << get<4>(now) + 1 << endl;
					return;
				}
			}
			else {
				if (vis[get<0>(now)][get<1>(now)][x][y]) continue;
				vis[get<0>(now)][get<1>(now)][x][y] = true;
				q.emplace_front(make_tuple(get<0>(now), get<1>(now), x, y, get<4>(now)));
			}
		}
	}
	cout << "NO" << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> (s[i] + 1);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (s[i][j] == 'M') sx_p = i, sy_p = j;
			else if (s[i][j] == 'P') sx = i, sy = j;
			else if (s[i][j] == 'K') ex = i, ey = j;
	bfs();
	return 0;
}
} // namespace liuzimingc

int main() {
	liuzimingc::main();
	return 0;
}

为什么会导致这样的性能差异呢？？？<tuple> 一直都比 struct 快吗？？？