P7775 [COCI 2009-2010 #2] VUK 题解

little_cindy · 2021-08-02 15:09:23 · 题解

橙名之后第一篇题解！

思路

题目的信息很明确，也十分简单，跑个 bfs 就行了。

可是，我们需要求出每一个点到最近的树的曼哈顿距离。

根据曼哈顿距离的定义，其实就是一个点到另一个点的最短路。所以，把所有树的位置放入队列，再用 bfs 求出最短路即可。

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
int mhd[maxn][maxn],n,m;
bool danger[maxn][maxn],vis[maxn][maxn];
struct wolf{
    int x;
    int y;
    int Manhattan_distance;//Vjekoslav 在逃回窝的途中离它最近的树的距离的最小值
    bool operator < (const wolf &tmp) const {//重载一下运算符
        return Manhattan_distance<tmp.Manhattan_distance;
    } 
};
struct node{
    int x,y,h;
}e,s;
int dx[4]={0,0,1,-1};//方向函数
int dy[4]={1,-1,0,0};
queue<node> nq;
void bfs1(){//求曼哈顿距离
    while(!nq.empty()){
        node cur=nq.front();
        nq.pop();
        mhd[cur.x][cur.y]=cur.h;
        for(int i=0;i<4;i++){
            int nx=cur.x+dx[i];
            int ny=cur.y+dy[i];
            if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&!danger[nx][ny]){
                danger[nx][ny]=1;
                nq.push({nx,ny,cur.h+1});
            }
        }
    }
    return;
}
int bfs(int x,int y){//求答案
    int ans=1e9;
    priority_queue<wolf> q;
    vis[x][y]=1;
    q.push({x,y,mhd[x][y]});
    while(!q.empty()){
        wolf cur=q.top();
        q.pop();
        if(cur.x==e.x&&cur.y==e.y) {//取最小答案
            ans=min(ans,cur.Manhattan_distance);
        }
        for(int i=0;i<4;i++){
            int nx=cur.x+dx[i];
            int ny=cur.y+dy[i];
            if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&!vis[nx][ny]){
                vis[nx][ny]=1;
                q.push({nx,ny,min(cur.Manhattan_distance,mhd[nx][ny])});
            }
        }
    }
    return ans;//返回答案
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char a;
            cin>>a;
            if(a=='+'){//树
                danger[i][j]=1;
                nq.push({i,j,0});
            }
            else if(a=='V'){//起点
                s={i,j};
            }
            else if(a=='J'){//终点
                e={i,j};
            }
        }
    }
    bfs1();
    cout<<bfs(s.x,s.y);
    return 0;
}