14.找路(简单搜索 BFS 最短步数)

找路

↑ 题目链接

题目

给定一个 \(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;
}