#1092 : Have Lunch Together 简单队列解法

0
0
#include<iostream>
#include<queue>
#include<algorithm>
#define N 105
char map[N][N],
int dist[N][N], vis[N][N], n, m;
using namespace std;
typedef struct point{ int r, c; point(int a, int b) :r(a), c(b){} }point;
queue<point> q;
void process(int i, int j,int d){
    if (i > 0 && i <= n&&j > 0 && j <= m ){
        if (vis[i][j] == 0)
        {
            if (map[i][j] == 'S'){
                dist[i][j] = d + 1;
            }
            if (map[i][j] == '.'){
                dist[i][j] = d + 1;
                q.push(point(i, j));
            }
            vis[i][j] = 1;
        }
    }
}
int getdist(int x, int y){
    if (x<1 || x>n || y<1 || y>m)return 0x3f3f3f3f;
    if (map[x][y] != 'S')return 0x3f3f3f3f;
    return dist[x][y];
}
void solve(){
    int hr, hc;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (map[i][j] == 'H'){
                hr = i;
                hc = j;
            }
        }
    }
    dist[hr][hc] = 0;
    vis[hr][hc] = 0;
    q.push(point(hr, hc));
    while (!q.empty())
    {
        point t = q.front();
        q.pop();
        process(t.r+1, t.c, dist[t.r][t.c]); 
        process(t.r-1, t.c, dist[t.r][t.c]);
        process(t.r, t.c+1, dist[t.r][t.c]);
        process(t.r, t.c-1, dist[t.r][t.c]);
    }
    int dmin=0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++){
            if (map[i][j] == 'S'){
                dmin = min(dmin, getdist(i,j+1) + dist[i][j]);
                dmin = min(dmin, getdist(i,j-1) + dist[i][j]);
                dmin = min(dmin, getdist(i-1,j)+ dist[i][j]);
                dmin = min(dmin, getdist(i+1,j) + dist[i][j]);
            }
        }
    }
    if (dmin<0x3f3f3f)cout << dmin;
    else cout << "Hi and Ho will not have lunch.";
}
int main(){
    memset(dist, 0x3f, sizeof(dist));
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

0 answer(s)

write answer 切换为英文 切换为中文


转发分享