• • 题目描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例：
      • 输出样例：
  • bfs最短路
    • 分析
    • 代码
    • 时间复杂度
  • 参考文章

题目传送门

题目描述

给定一个 nn 行 mm 列的方格矩阵。

其中有些方格是空地（可以进入），有些方格是餐厅（可以进入），有些方格是障碍（不可进入）。

开始时，小 YY 和小 MM 各自位于一个空地方格中。

每个人都可以沿上下左右四个方向进行移动，移动一格距离需要花费 1111 分钟时间。

他们希望选择一家餐厅进行聚餐，要求两人从各自出发点到达该餐厅所花费的时间之和尽可能小。

输出这个最小时间和。

输入格式

输入包含多组测试数据。

每组数据第一行包含两个整数 n,mn,m。

接下来 nn 行，包含一个 n×mn×m 的字符矩阵。

矩阵中只包含以下五种字符：

• # 表示障碍方格。
• . 表示空地方格。
• Y 表示小 YY 所在的空地方格，有且仅有一个。
• M 表示小 MM 所在的空地方格，有且仅有一个。
• @ 表示餐厅。

输出格式

每组数据输出一行答案，表示最小时间和。

保证一定有解。

数据范围

最多包含 100100 组数据。
2≤n,m≤2002≤n,m≤200。

输入样例：

4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#

输出样例：

66
88
66

bfs最短路

分析

分别求出Y到每个@的最短距离、M到每个@的最短距离

然后遍历每个@，求出Y，M到这个@的最短距离之和，求个最小的就可以

需要注意的是我这里将dist初始化成-1，所以最后一步遍历@求最小和的时候，不能这么做

        int res = 0x3f3f3f3f;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; ++j)
            {
                if(g[i][j] == '@') // 注意这里因为一开始初始化成了-1！！所以要特判
                {
                    int t = disty[i][j] + distm[i][j];
                    res = min(res, t);
                }

            }
        }

因为会有这种情况，这里的@距离是-1！！！

####
#@##
####

所以改成这种

        int res = 0x3f3f3f3f;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; ++j)
            {
                if(g[i][j] == '@' && distm[i][j] > 0 && disty[i][j] > 0) // 注意这里因为一开始初始化成了-1！！所以要特判
                {
                    int t = disty[i][j] + distm[i][j];
                    res = min(res, t);
                }

            }
        }
        printf("%d\n", res * 11);

因为是求最短距离

所以最好的方式还是一开始就将所有dist初始化为0x3f3f3f3f

代码

#include
#include
#include
#include
using namespace std;
typedef pair PII;
const int N = 210;

int disty[N][N];
int distm[N][N];
int T, n, m;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
char g[N][N];

void bfs(int dist[N][N], int ax, int ay)
{
    // memset(dist, -1,sizeof dist);

    queue q;
    q.push({ax, ay});
    dist[ax][ay] = 0;

    while(q.size())
    {
        PII t = q.front();
        q.pop();
        int x = t.first, y = t.second;
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] != '#' && dist[nx][ny] == -1)
            {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    for(int i = 0; i < n;  i++)
    {
        for(int j = 0; j < m; j++)
        {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
}


int main()
{
    while(cin >> n >> m)
    {
        int xy,yy, xm, ym;

        for(int i = 0; i < n; i++)
            scanf("%s", g[i]);

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(g[i][j] == 'Y') xy = i, yy = j;
                else if(g[i][j] == 'M') xm = i, ym = j;

        memset(disty, -1, sizeof disty);
        memset(distm, -1, sizeof distm);

        bfs(disty, xy, yy);
        bfs(distm, xm, ym);

        int res = 0x3f3f3f3f;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; ++j)
            {
                if(g[i][j] == '@' && distm[i][j] > 0 && disty[i][j] > 0) // 注意这里因为一开始初始化成了-1！！所以要特判
                {
                    int t = disty[i][j] + distm[i][j];
                    res = min(res, t);
                }

            }
        }
        printf("%d\n", res * 11);
    }
    return 0;
}

时间复杂度

参考文章