顺便带杯奶茶

问题讨论区 基础段
1

题目描述

暑假的某一天，鱼大大和他的朋友鸿大大约好了去鸿大大家里玩耍。这天鱼大大准备要出门的时候，鸿大大突然请求鱼大大顺路去奶茶店买杯奶茶一起带过来，热心的鱼大大当然是选择帮忙啦，不过为了节约时间，尽快和鸿大大玩耍，鱼大大会先线上订好奶茶，然后会在最短时间走到奶茶店，带上奶茶，再到达鸿大大的家里。现问鱼大大最少需要多少时间能到达鸿大大家里？

注：鱼大大移动一步需要花费一分钟，每次只会往上下左右某个方向移动一步

鱼大大线上订奶茶时间和在奶茶店打包带走奶茶的时间不计入总时间

地图上只有一家奶茶店

输入格式

第一行包含两个整数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 dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
int n, m, e = INT_MAX;
char mp[205][205];
int vis1[205][205], vis2[205][205];
struct node
{
    int x, y, step;
};
int A, B, C, D;
void bfs(int x, int y, int vis[205][205])
{
    queue<node> q;
    vis[x][y] = 1;
    q.push({ x, y, 0 });
    while (q.size())
    {
        node hd = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int r = hd.x + dx[i];
            int c = hd.y + dy[i];
            int step = hd.step + 1;
            if (r < 1 || c < 1 || r > n || c > m || mp[r][c] == '#' || vis[r][c])
                continue;
            vis[r][c] = step;
            q.push({ r, c, step });
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> mp[i][j];
            if (mp[i][j] == 'Y')
            {
                A = i;
                B = j;
            }
            if (mp[i][j] == 'Q')
            {
                C = i;
                D = j;
            }
        }
    }
    bfs(A, B, vis1);
    bfs(C, D, vis2);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (mp[i][j] == 'H' && vis1[i][j] && vis2[i][j])
                e = min(e, vis1[i][j] + vis2[i][j]);
    if (e == INT_MAX)
        cout << "no way";
    else
        cout << e;
    return 0;
}
2

大佬在吗

3

阿弥诺斯

4

你这写的

5

是从鱼大大家去奶茶店
再从奶茶店去鸿大大家

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (mp[i][j] == 'H' && vis1[i][j] && vis2[i][j])
                e = min(e, vis1[i][j] + vis2[i][j]);

这个什么意思

鱼大大家到鸿大大家 + 奶茶店到鸿大大家

6

:sweat_smile::sweat_smile::sweat_smile:

7

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[110][110];
int v[110][110];
int sum=0;
int f=0;
struct node
{
int x;
int y;
int cnt;
}q,s,h;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void bfs(int x1,int y1,int x2,int y2)
{
queue qu;
qu.push({x1,y1,0});
v[x1][y1]++;

while(!qu.empty())
{
	node now=qu.front();
	qu.pop();
	if(到达)
	{
		执行语句（什么语句自己想）
		return;
	}
	for(int i=0;i<4;i++)
	{
		int nx=now.x+dx[i];
		int ny=now.y+dy[i];
		int count=now.cnt+1;
		if(如果不能走)continue;
		标记+入队

	}	
}

}
int main()
{

cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
这些是存相应地点的坐标的
if(a[i][j]==‘Q’)
{
q.x=i;
q.y=j;
}
if(a[i][j]==‘Y’)
{
s.x=i;
s.y=j;
}
if(a[i][j]==‘H’)
{
h.x=i;
h.y=j;
}
}

}
bfs(传入地点);
for(int i=1;i<=n;i++)
{
	for(int j=1;j<=m;j++)
	{
		v[i][j]=0;初始化标记数组
	}
}
bfs(传入地点);
if(f==2)cout<<sum<<endl;
else cout<<"no way"<<endl;
return 0;

}

8

@鲁子欣 两次bfs，你的函数加一个：

if(a[r][c]=='Q'){
		e+=q.front().step;
		return ;
	}

然后把改完的函数复制一遍，把"Q"改成’H’就可以了

1 个赞