Skip to content

14175: 【原4175】酒吧

题目

题目描述

author: Yifan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4175

题目描述

莘庄有很多酒吧,侯不会和苏前端打算约在其中一个酒吧见面。为了节省时间,他们希望从各自的家赶往酒吧的时间之和尽可能少,现在请你为他们挑选一个酒吧。莘庄可以被划分为\(n \times m\)个单元格,每个单元格可能是侯不会的家('H')、苏前端的家('S')、障碍物('#')、空地('.')或者酒吧('B'),其中障碍物所在位置不能通行,其余单元格均可通行,保证至少有一个酒吧两人都可以到达。侯不会和苏前端每分钟可以向上下左右移动一格。求侯不会和苏前端各自从家到酒吧的时间之和的最小值。

输入格式

第一行包含两个整数n, m。(\(2 \le n, m \le 1000\)) 接下来n行,每行有m个用空格隔开的字符。 'H'代表侯不会的家的位置。 'S'代表苏前端的家的位置。 '#'代表障碍物的位置。 '.'代表可通行的位置。 'B'代表酒吧的位置。

输出格式

一个整数,表示侯不会和苏前端各自从家到酒吧的时间之和的最小值。

样例输入

4 4
H.#B
....
.#..
B..S

样例输出

6

数据范围

对于20%的数据,\(2 \le n, m \le 20\)。 对于另外20%的数据,地图上没有障碍物。 对于另外20%的数据,地图上只有一个酒吧。 对于100%的数据,\(2 \le n, m \le 1000\)。

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
char s[1005][1005];
int d1[1005][1005], d2[1005][1005];
bool vis[1005][1005];
queue<int> qx, qy;
void bfs(int xxx, int yyy, int d[][1005]){
    qx.push(xxx), qy.push(yyy);
    d[xxx][yyy] = 0;
    memset(vis, 0, sizeof(vis));
    vis[xxx][yyy] = true;
    while (!qx.empty()){
        int cx = qx.front(), cy = qy.front();
        qx.pop(), qy.pop();
        for (int i = 0; i < 4; ++i){
            int ex = cx + dx[i], ey = cy + dy[i];
            if (ex < 0 || ex >= n || ey < 0 || ey >= m)
                continue;
            if (vis[ex][ey] || s[ex][ey] == '#') continue;
            d[ex][ey] = d[cx][cy] + 1;
            qx.push(ex), qy.push(ey);
            vis[ex][ey] = true;
        }
    }
}
void init(){
    scanf("%d%d", &n, &m);
    if (n <= 20){
        for (int i = 0; i < n; ++i)
            scanf("%s", s[i]);
    }else {
        char o[10];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j){
                scanf("%s", o);
                s[i][j] = o[0];
            }
    }

}
void solve(){
    int stx1, stx2, sty1, sty2;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j){
            if (s[i][j] == 'H') stx1 = i, sty1 = j;
            if (s[i][j] == 'S') stx2 = i, sty2 = j;
        }
    memset(d1, 0x3f, sizeof(d1));
    memset(d2, 0x3f, sizeof(d2));
    bfs(stx1, sty1, d1);
    bfs(stx2, sty2, d2);
    int ans = INF;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (s[i][j] == 'B' && d1[i][j] < 0x3f3f3f3f && d2[i][j] < 0x3f3f3f3f){
                if (d1[i][j] + d2[i][j] < ans)
                    ans = d1[i][j] + d2[i][j];
            }
    printf("%d\n", ans) ;
}
int main(){
    init();
    solve();
    return 0;
}