题解
使用BFS求出两个人到达每个刷新点的最短时间,枚举每个刷新点根据已有记录求最小时间和即可。
注意不可到达的点的所需时间应为无穷大。
AC代码
#include <stdio.h>
#include <bits/stdc++.h>
#define fst first
#define sed second
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 210;
int dir[4][2] = { -1, 0, 1, 0, 0, -1, 0, 1 };
char g[N][N];
int p[N][N], q[N][N], px, py, qx, qy;
bool vis[N][N];
int n, m;
struct node
{
int x, y, k;
};
void BFS(int d[][N], int xx, int yy)
{
memset(vis, 0, sizeof(vis));
queue<node> q;
q.push({ xx, yy, 0 });
vis[xx][yy] = 1;
d[xx][yy] = 0;
while (!q.empty())
{
int x = q.front().x, y = q.front().y, k = q.front().k + 1; q.pop();
for (int i = 0; i < 4; ++i)
{
xx = x + dir[i][0], yy = y + dir[i][1];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[xx][yy] != '#' && !vis[xx][yy])
q.push({ xx, yy, k }), vis[xx][yy] = 1, d[xx][yy] = k;
}
}
}
int main()
{
#ifdef LOCAL
freopen("C:/input.txt", "r", stdin);
#endif
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = 1; i <= n; ++i)
{
scanf("%s", g[i] + 1);
for (int j = 1; j <= m; ++j)
if (g[i][j] == 'Y')
px = i, py = j, g[i][j] = '.';
else if (g[i][j] == 'M')
qx = i, qy = j, g[i][j] = '.';
}
memset(p, 0x3f, sizeof(p));
memset(q, 0x3f, sizeof(q));
BFS(p, px, py);
BFS(q, qx, qy);
int ans = INF;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (g[i][j] == '@')
ans = min(ans, p[i][j] + q[i][j]);
printf("%d\n", ans * 11);
}
return 0;
}