P7775 [COCI2009-2010#2] VUK

· · 算法·理论

P7775 [COCI2009-2010#2] VUK

题目任意门

这道题卡了我三天

觉得很有必要消化一下

题目

这道题中有个使得 Vjekoslav 在途中离它最近的树的距离的最小值最大 一看就是二分

分析

考虑到时间复杂度 所以肯定得预处理一下 因为要求距离 所以用个二维存每个点与最近的树的距离 比较推荐BFS

memset(a, 63, sizeof(a));//假设自己是最大 
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++) {
            if(mp[i][j] == '+' ) {
                q.push({i, j});//存队列 
                a[i][j] = 0;//树为0 
            }
            if(mp[i][j] == 'V') sx = i, sy = j;//记V,J坐标 
            if(mp[i][j] == 'J') tx = i, ty = j;
        }
    }
    while(!q.empty()){
        x = q.front().x, y = q.front().y;
        q.pop();
        for(j=0; j<=3; j++){
            int nx = x + dx[j], ny = y + dy[j];
            if(a[nx][ny] > a[x][y] + 1 && nx>=1 && nx<=n && ny>=1 && ny<=m){//预处理 记得判断边界 
                a[nx][ny] = a[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

然后二分就AC啦

代码

代码如下

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
//ll k,n,m,a,b,vis[505][505],mi[545147]={545147},cjdd[545147],ss=-1,ss1=-1,sss,ch[505][505];
//ll bb1,bb2=250000,V=545145,J=545146;
//ll vip[505][505],vx,jx,vy,jy,vip12[505][505];
//bool f=false;
//vector <fff> v[1005];
//vector <int> ve[1005];
int i, j, k, m, n, x, y, l, r, sx, sy, tx, ty, ans;
int a[505][505], vis[505][505];
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
char mp[505][505];
struct fish{
    ll x,y;
};
queue <fish> q;
bool check(int s){
    memset(vis, 0, sizeof(vis));//清零 
    q.push({sx, sy}), vis[sx][sy] = 1;
    while(!q.empty()){
        x = q.front().x, y = q.front().y;
        q.pop();
        for(j=0; j<=3; j++){
            int nx = x + dx[j], ny = y + dy[j];
            if(nx>=1 && nx<=n && ny>=1 && ny<=m && vis[nx][ny] == 0 && a[nx][ny] >= s){
                vis[nx][ny] = 1;//标记 
                q.push({nx, ny});
            }
        }
    }
    return vis[tx][ty] == 1;
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%s", mp[i]+1);
    }
    memset(a, 63, sizeof(a));//假设自己是最大 
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++) {
            if(mp[i][j] == '+' ) {
                q.push({i, j});//存队列 
                a[i][j] = 0;//树为0 
            }
            if(mp[i][j] == 'V') sx = i, sy = j;//记V,J坐标 
            if(mp[i][j] == 'J') tx = i, ty = j;
        }
    }
    while(!q.empty()){
        x = q.front().x, y = q.front().y;
        q.pop();
        for(j=0; j<=3; j++){
            int nx = x + dx[j], ny = y + dy[j];
            if(a[nx][ny] > a[x][y] + 1 && nx>=1 && nx<=n && ny>=1 && ny<=m){//预处理 记得判断边界 
                a[nx][ny] = a[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    l = 0, r = min(a[sx][sy], a[tx][ty]);
    while(l <= r){
        int mid = (l + r) / 2;
        if(check(mid)){
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    printf("%d", ans);
    return 0;
}