「NOIp2017」奶酪-记忆化搜索

因为作者太菜了所以无法简洁高效的描述题目

Links

Luogu P3958

Solution

可以一眼看出,这道题可以使用搜索做

直接从进入奶酪的洞开始,搜索扩展至一个出奶酪的洞

因为有可能有多条路径都通向一条死路,所以可以使用记忆化的方法来避免多次向同一条死路扩展

Code

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=1000+5;
int book[maxn];
int T;
int n,h,r;
bool ans=false;
struct node{
    int x;
    int y;
    int z;
    int flag;//此处的flag是一个标志位,标记该点能否作为起点,避免不必要的搜索
}a[maxn];
inline int dist(node a,node b){
    double tmp=sqrt((double)pow(a.x-b.x,2)+(double)pow(a.y-b.y,2)+(double)pow(a.z-b.z,2));
    return tmp<=2*r;
}
void dfs(node t,int step){
    book[step-1]=1;
    if(t.z+r>=h){
        ans=true;
        return;
    } 
    for(int i=1;i<=n;i++){ 
    	if(!book[i] && dist(a[i],t)) dfs(a[i],i+1);
        if(ans) return;
    }
}
bool cmp(node x,node y){	
    return x.z<=y.z;
}
int main(){
    scanf("%d",&T);
    while(T){
        scanf("%d%d%d",&n,&h,&r);
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
            if(abs(a[i].z)<=r) a[i].flag=1;
            else a[i].flag=0;
        } 
        sort(a+1,a+n+1,cmp);
        memset(book,0,sizeof(book));
        ans=false;	
        for(int i=1;i<=n;i++){
            if(a[i].flag) dfs(a[i],i+1);
            if(ans) break;
        }
        if(ans){ 
            printf("Yes\n");
        }else printf("No\n");	
        T--;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注