$$\color{Purple}{kuangbin题解目录}$$
描述
给定一个 $n$ 行 $m$ 列的方格矩阵。
其中有些方格是空地(可以进入),有些方格是餐厅(可以进入),有些方格是障碍(不可进入)。
开始时,小 $Y$ 和小 $M$ 各自位于一个空地方格中。
每个人都可以沿上下左右四个方向进行移动,移动一格距离需要花费 $11$ 分钟时间。
他们希望选择一家餐厅进行聚餐,要求两人从各自出发点到达该餐厅所花费的时间之和尽可能小。
输出这个最小时间和。
输入格式
输入包含多组测试数据。
每组数据第一行包含两个整数 $n,m$。
接下来 $n$ 行,包含一个 $n×m$ 的字符矩阵。
矩阵中只包含以下五种字符:
#
表示障碍方格。.
表示空地方格。Y
表示小 $Y$ 所在的空地方格,有且仅有一个。M
表示小 $M$ 所在的空地方格,有且仅有一个。@
表示餐厅。
输出格式
每组数据输出一行答案,表示最小时间和。
保证一定有解。
数据范围
最多包含 $100$ 组数据。
$2 \\le n,m \\le 200$。
输入样例:
4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#
输出样例:
66
88
66
思路
分别跑两个人的$bfs$,用$dist1$数组存储第一个人的行走情况,用$dist2$数组存储第二个人的行走情况,最后枚举所有的餐馆取$11 \times (dist1+dist2)$最小值即可.
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#define MAXN 210
using namespace std;
const int inf=0x3f3f3f3f;
int n,m;
struct node{
int x;
int y;
};
int sx1,sy1,sx2,sy2;
char g[MAXN][MAXN];
int dist1[MAXN][MAXN],dist2[MAXN][MAXN],dist[MAXN][MAXN];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
void bfs(int sx,int sy)
{
//memset(dist,0x3f,sizeof(dist));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dist[i][j]=inf;
queue<node> q;
q.push({sx,sy});
dist[sx][sy]=0;
while(q.size()>0)
{
node temp=q.front();
q.pop();
for(int i=0;i<=3;i++)
{
int dx=temp.x+dir[i][0],dy=temp.y+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&dist[dx][dy]==inf&&g[dx][dy]!='#')
{
q.push({dx,dy});
dist[dx][dy]=dist[temp.x][temp.y]+1;
}
}
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
vector<node> v;
for(int i=1;i<=n;i++)
{
scanf("%s",g[i]+1);
for(int j=1;j<=m;j++)
{
if(g[i][j]=='Y')
sx1=i,sy1=j;
else if(g[i][j]=='M')
sx2=i,sy2=j;
else if(g[i][j]=='@')
v.push_back({i,j});
}
}
bfs(sx1,sy1);
//memcpy(dist1,dist,sizeof(dist));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dist1[i][j]=dist[i][j];
bfs(sx2,sy2);
//memcpy(dist2,dist,sizeof(dist));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dist2[i][j]=dist[i][j];
int res=inf;
for(int i=0;i<v.size();i++)
res=min(res,11*(dist1[v[i].x][v[i].y]+dist2[v[i].x][v[i].y]));
printf("%d\n",res);
}
return 0;
}