找路
↑ 题目链接
题目
给定一个 \(n\) 行 \(m\) 列的方格矩阵。其中有些方格是空地（可以进入），有些方格是餐厅（可以进入），有些方格是障碍（不可进入）。开始时，小 \(Y\) 和小 \(M\) 各自位于一个空地方格中。每个人都可以沿上下左右四个方向进行移动，移动一格距离需要花费 \(11\) 分钟时间。他们希望选择一家餐厅进行聚餐，要求两人从各自出发点到达该餐厅所花费的时间之和尽可能小。输出这个最小时间和。
输入格式
输入包含多组测试数据。
每组数据第一行包含两个整数 \(n,m\)
接下来 \(n\) 行，包含一个 \(n×m\) 的字符矩阵。
矩阵中只包含以下五种字符：
# 表示障碍方格。
. 表示空地方格。
Y 表示小 Y
所在的空地方格，有且仅有一个。
M 表示小 M
所在的空地方格，有且仅有一个。
@ 表示餐厅。
输出格式
每组数据输出一行答案，表示最小时间和。
保证一定有解。
数据范围
最多包含 \(100\) 组数据。\(2≤n,m≤200\)
输入样例：
4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#
输出样例：
66
88
66
思路
两次 \(BFS\) 分别搜索最短步数，最后更新最小值
代码
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=210;
int d1[N][N],d2[N][N];
char g[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int n,m;
void bfs(int sx,int sy,int d[][N])
{
memset(d,-1,sizeof d1);
queue<PII>q;
q.push({sx,sy});
d[sx][sy]=0;
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int a=t.x+dx[i],b=t.y+dy[i];
if(a<0||a>=n||b<0||b>=m||d[a][b]!=-1||g[a][b]=='#')continue;
d[a][b]=d[t.x][t.y]+1;
q.push({a,b});
}
}
}
int main()
{
while(cin>>n>>m)
{
int yx,yy,mx,my;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>g[i][j];
if(g[i][j]=='Y')yx=i,yy=j;
if(g[i][j]=='M')mx=i,my=j;
}
bfs(yx,yy,d1);
bfs(mx,my,d2);
int ans=1e9;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(g[i][j]=='@'&&d1[i][j]!=-1&&d2[i][j]!=-1)
{
ans=min(ans,d1[i][j]+d2[i][j]);
}
cout<<ans*11<<endl;
}
return 0;
}