PTA - 구원 007 (BFS)

5219 단어 BFS데이터 구조DFS\BFS
오래된 영화 '007 의 생사 의 고비' (Live and Let Die) 에서 007 이 마 약사 범 에 게 악어 못 중심의 작은 섬 에 잡 혀 그 는 아주 대담 한 방법 으로 탈출 했다. 연못 속 악어 들 의 큰 머리 를 밟 고 해안 으로 뛰 어 올 랐 다!(그 당시 스턴트맨 은 마지막 악어 에 게 발 을 물 렸 다 고 한다. 다행히 두 꺼 운 장 화 를 신고 도 망 쳤 다.) 악어 풀 은 길이 가 100 미터 인 사각형 이 고 중심 좌 표 는 (0, 0) 이 며 동북 각 좌 표 는 (50, 50) 이다.지심 도 는 (0, 0) 을 원심 으로 하고 지름 15m 의 원 이다.연못 에 분포 되 어 있 는 악어 의 좌표 와 007 번 점프 할 수 있 는 최대 거 리 를 정 해 주 었 다. 그 에 게 생 천 을 탈출 할 수 있 는 지 알려 줘 야 한다.입력 형식: 우선 첫 줄 에 두 개의 정수: 악어 수량 N (≤ 100) 과 007 번 점프 할 수 있 는 최대 거리 D 를 드 립 니 다.그 다음 에 N 줄 에서 줄 마다 악어 (x, y) 좌 표를 드 립 니 다.주의: 악어 두 마리 가 같은 점 에 있 지 않 습 니 다.출력 형식: 007 이 탈출 할 수 있 으 면 한 줄 에 "Yes" 를 출력 합 니 다. 그렇지 않 으 면 "No" 를 출력 합 니 다.입력 샘플 1: 14 20 25 - 15 - 25 28 49 29 15 - 35 - 25 28 27 - 29 - 8 - 28 - 20 - 35 - 25 - 20 - 13 29 - 30 15 - 35 40 12 12 출력 샘플 1: Yes 입력 샘플 2: 4 13 - 12 12 12 12 12 - 12 12 출력 샘플 2: No
사고의 방향
길이 가 100 인 악어 못 007 은 (0, 0) 을 중심 으로 지름 이 15 인 둥 근 섬 에서 악어 머리 를 밟 고 밖으로 뛰 어 나 와 연못 에서 뛰 어 나 올 수 있 는 지 를 구 해 야 한다. 경기 할 때 제목 을 단번에 읽 지 못 했 고 악 어 를 밟 고 밖으로 뛰 어 나 가 는 것 을 보지 못 했다. 사실은 BFS 였 다.
시합 후에 아주 좋 은 도 해 를 보 았 다.
AC 코드
#include 
#include 
#include 
#include 
#include 
#include 
#define mst(a) memset(a, 0, sizeof(a))

using namespace std;
const int maxn = 105;
int vis[maxn];
int n, d;

struct save007{
    int x, y;
    double dd;
};
save007 p[maxn];

double dis( int x, int y ){
    return sqrt(x*x+y*y) - 15;
}

bool win( int x, int y ){
    if( x + d >= 50 || y + d >= 50 || x - d <= -50 || y - d <= -50 )
        return true;
    return false;
}

void BFS(){
    queue que;
    for( int i = 0; i < n; i++ ){
        if( p[i].dd <= d ){
            que.push(p[i]);
            vis[i] = 1;
        }
    }
    while( !que.empty() ){
        save007 node = que.front();
        if( win( node.x, node.y ) ){
            puts("Yes");
            return;
        }
        que.pop();
        for( int i = 0; i < n; i++ ){
            if( !vis[i] && node.dd + d >= p[i].dd ){
                que.push(p[i]);
                vis[i] = 1;
            }
        }
    }
    printf("No
");
    return;
}

void solve(){
    if( d >= 50 - 7.5 )  printf("Yes
");
    else BFS();
    return;
}

int main()
{
    mst(vis);
    mst(p);
    scanf("%d%d",&n,&d);
    for( int i = 0; i < n; i++ ){
        scanf("%d%d",&p[i].x, &p[i].y);
        p[i].dd = dis(p[i].x, p[i].y);
    }
    solve();
    return 0;
}
Generics(2)
[알고리즘] 중복단어 제거

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage