顺便带杯奶茶 题目ID：9749
题目描述
暑假的某一天，鱼大大和他的朋友鸿大大约好了去鸿大大家里玩耍。这天鱼大大准备要出门的时候，鸿大大突然请求鱼大大顺路去奶茶店买杯奶茶一起带过来，热心的鱼大大当然是选择帮忙啦，不过为了节约时间，尽快和鸿大大玩耍，鱼大大会先线上订好奶茶，然后会在最短时间走到奶茶店，带上奶茶，再到达鸿大大的家里。现问鱼大大最少需要多少时间能到达鸿大大家里？
注：鱼大大移动一步需要花费一分钟，每次只会往上下左右某个方向移动一步
鱼大大线上订奶茶时间和在奶茶店打包带走奶茶的时间不计入总时间
地图上只有一家奶茶店
输入格式
第一行包含两个整数n，m。接下来的n行，每行输入m个字符来表示地图。
“Y”表示鱼大大的家。
“H”表示鸿大大的家。
“Q”表示奶茶店。
“#”是障碍。
‘.’，‘Y’，‘H’和’Q’，这些位置都可以通过。
输出格式
输出鱼大大到达鸿大大家里的最少时间，若无法买到奶茶并到达则输出“no way”
样例
Input 1
8 10
#.##.Q.#.#
.#.#..###.
..#...#..#
.###......
#..Y..##.#
..#...#.#.
#.##.#####
.##.H..##.
Output 1
14
Input 2
8 10
#.##...#Q#
.#.#..###.
..#...#..#
.###......
#..Y..##.#
..#...#.#.
#.##.#####
.##.H..##.
Output 2
no way
样例解释
样例1：鱼大大先从Y出发，按最短路走到Q，花费6分钟，取到奶茶后，从Q出发，按最短路走到H，花费8分钟。
样例2：鱼大大先从Y出发，无法走到奶茶店Q，输出 no way
数据范围
2 ≤n,m ≤100
在线等
#include <bits/stdc++.h>
using namespace std;
int n,m,stx,sty,enx,eny,stx1,sty1,enx1,eny1;
int vis[1005][1005];
char mapn[1005][1005];
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
struct node{
int x,y,cnt;
};
void bfs(int x,int y){
queue<node> qu;
qu.push({x,y,0});
while(!qu.empty()){
node now=qu.front();
qu.pop();
for(int i=0;i<4;i++){
int now_x=now.x+dx[i];
int now_y=now.y+dy[i];
int now_cnt=now.cnt+1;
if(now_x<1||now_y<1||
now_x>n||now_y>m||
vis[now_x][now_y]!=-1&&vis[now_x][now_y]<=now_cnt||
mapn[now_x][now_y]=='#'){
continue;
}
qu.push({now_x,now_y,now_cnt});
vis[now_x][now_y]=now_cnt;
}
}
}
int main(){
cin.sync_with_stdio(0);
cin.tie(0);
memset(vis,0x3f,sizeof(vis));
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mapn[i][j];
if(mapn[i][j]=='Y'){
stx=i;
sty=j;
vis[i][j]=0;
}
if(mapn[i][j]=='Q'){
enx=i;
eny=j;
stx1=i;
sty1=j;
}
if(mapn[i][j]=='H'){
enx1=i;
eny1=j;
}
}
}
bfs(stx,sty);
int sum=vis[enx][eny];
stx=stx1,sty=sty1,enx=enx1,eny=eny1;
memset(vis,0x3f,sizeof(vis));
vis[stx][sty]=0;
bfs(stx,sty);
if(vis[enx][eny]!=1061109567) cout<<vis[enx][eny]+sum;
else cout<<"no way";
return 0;
}
