3.相约全家

常规
1

3. 相约全家

XJOI - 题目ID：3586选做题100分

最新提交：0 分

历史最高：0 分

时间限制: 1000ms

空间限制: 131072kB

题目描述

时间限制：1s 空间限制：128M

题目描述：

暑假即将到来，你和你的朋友计划吃肯德基。但是在地图上有很多肯德基，所以你应该想办法选择一个。

方法是：计算从你家到一个肯德基的距离，以及从你朋友家到这个肯德基的距离，如果这两个距离之和是所有离肯德基的距离中最小的一个，那么你们选择这家。

输入格式：

第一行包含两个整数 �n 和 �m。

接下来的 �n 行，每行输入 �m 个字符来表示地图。(1≤�, �≤200)(1≤n, m≤200)

‘@’ 是你的位置，‘＃’ 是障碍，‘F’ 表示肯德基，‘＆’ 表示您朋友的位置。

‘.’，‘F’，‘@’ 和 ‘＆’，这些位置都可以通过。

输出格式：

如果你能找到一条可行的路径到达肯德基，输出你和你的朋友选择的最少路程，否则输出 “Meeting cancelled”（没有任何一家肯德基可以让两人相约）。

样例输入1：

4 4 @.#F … .#… F…&

样例输出1：

6

样例输入2：

4 4 &.#F … .#… F#.@

样例输出2：

8

2 个赞
2

这不是水题吗？

1 个赞
3

思路：
马的遍历做过吧？两个bfs，分别用两个二维数组存步数（开始初始化成-1）

1 个赞
4 
for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='F' and ans1[i][j]!=-1 and ans2[i][j]!=-1){
				ans=min(ans,ans1[i][j]+ans2[i][j]);
			}
		}
	}

其他你应该会了吧？（a是地图数组）

1 个赞
5 
#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int n, m, minans = 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]);
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] == '@')
            {
                A = i;
                B = j;
            }
            if (mp[i][j] == '&')
            {
                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] == 'F' && vis1[i][j] && vis2[i][j]) // 是KFC且都能到
                minans = min(minans, vis1[i][j] + vis2[i][j]);
    if (minans == INT_MAX) // 不能相约    minans未改变
        cout << "Meeting cancelled";
    else
        cout << minans;
}
void bfs(int x, int y, int vis[205][205])
{
    queue<node> que; 
    vis[x][y] = 1;   // 标记起点
    que.push({x, y, 0});
    while (que.size()) // 队列非空 一直搜索
    {
        node hd = que.front();
        que.pop();
        for (int i = 0; i < 4; i++) // 遍历4个方向
        {
            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;       // 标记新点
            que.push({r, c, step}); // 新点新步数入队
        }
    }
}
2 个赞
6

你好，非必要时请别直接发代码

1 个赞