首页 > 其他 > 详细

06-图2 Saving James Bond - Easy Version

时间:2019-04-17 15:26:15      阅读:150      评论:0      收藏:0      [点我收藏+]
#include <cstdio>
#include <cmath>
const int diameter = 15;
const int maxn = 100;
int D, Ncro;
int Visted[maxn] = {0};

struct coordinates {
    int x, y;
} cro_pos[maxn];

coordinates O;


void init(int Ncro);
bool jumpJudge(coordinates a, coordinates b);
bool arrive(int i);
bool firstJudge(coordinates a, coordinates b);
int DFS(int vertex);
bool reachBank(int vertex);

int main() {
    scanf("%d %d", &Ncro, &D);
    init(Ncro);
    
    int ans = 0;
    for (int i=0; i<Ncro; i++) {
        if ( !Visted[i] and firstJudge(cro_pos[i], O) ) {
            ans = DFS(i);
            if(ans == 1) break;
        }
    }
    if (ans == 1) {
        printf("Yes\n");
    }
    else printf("No\n");
    
    return 0;
}

int DFS(int vertex) {
    int ans = 0;
    Visted[vertex] = 1;
    
    if ( reachBank(vertex) ) {
        return 1;
    }
    for(int i=0; i<Ncro; i++) {
        if( !Visted[i] and jumpJudge(cro_pos[i], cro_pos[vertex]) )
            ans = DFS(i);
        if (ans == 1) {
            break;
        }
    }
    
    return ans;
}

bool reachBank(int vertex) {
    int ans = 0;
    
    if (fabs(cro_pos[vertex].x - 50) <= D) {
        ans =  1;
    }
    
    if (fabs(cro_pos[vertex].x + 50) <= D) {
        ans =  1;
    }
    
    if (fabs(cro_pos[vertex].y + 50) <= D) {
        ans =  1;
    }
    
    if (fabs(cro_pos[vertex].y - 50) <= D) {
        ans = 1;
    }
    
    return ans;
}




void init(int Ncro) {
    for (int i=0; i<Ncro; i++) {
        scanf("%d%d", &cro_pos[i].x, &cro_pos[i].y);
    }
    O.x = 0;
    O.y = 0;
}

bool jumpJudge(coordinates a, coordinates b) {
    if ( sqrt( pow(a.x - b.x, 2) + pow(a.y - b.y, 2) ) <= D) {
        return true;
    }
    else return false;
}


bool firstJudge(coordinates a, coordinates b) {
    if (sqrt( pow(a.x - b.x, 2) + pow(a.y - b.y, 2) ) <= D + diameter/2) {
        return  true;
    }
    return false;
}

 

06-图2 Saving James Bond - Easy Version

原文:https://www.cnblogs.com/acoccus/p/10723690.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!