uva225 回溯剪枝

时间：2022-07-11 21:39:23

这道题要剪枝，不然会超时，还有就是每次参加过的城市下次不能再参观，不然会WA。

对于障碍物的坐标我用了两种方法，第一种就是直接用STL里面的set，对于判断是否访问过直接用的count，用时960ms；当我把集合换成数组，200ms通过。

用set的AC代码：

#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=300;
int dx[]={1,0,0,-1,5};
int dy[]={0,1,-1,0,5}; //east,north,south,west
char dir[]="ensw";
int vis[maxn][maxn];
int n,cnt;
struct node{
    int x,y;
    node(int x=0,int y=0):x(x),y(y){}
    bool operator < (const node &p) const{
        return x>p.x||(x==p.x&&y>p.y);
    }
};
set<node>u;

void dfs(int *a,int cur,int d,node pos){
    if(cur==n&&pos.x==150&&pos.y==150){
        cnt++;
        for(int i=0;i<n;++i) printf("%c",dir[a[i]]);
        printf("\n");
        return;
    }
    if(cur>=n) return;
    if((abs(pos.x-150)+abs(pos.y-150))>((n-cur)*(n+cur+1)/2)) return; //cut
    for(int i=0;i<4;++i){
        if(dx[i]==dx[d]||dy[i]==dy[d]) continue;
        int newx=pos.x+(cur+1)*dx[i],newy=pos.y+(cur+1)*dy[i];
        if(vis[newx][newy]) continue; //已经旅游过
        int flag=0,c,p;
        if(newx==pos.x){
            c=min(newy,pos.y),p=max(newy,pos.y);
            for(int k=c;k<=p;++k){
                node newc(newx,k);
                if(u.count(newc)) {flag=1;break;}
            }
        }
        else if(newy==pos.y){
            c=min(newx,pos.x),p=max(newx,pos.x);
            for(int k=c;k<=p;++k){
                node newc(k,newy);
                if(u.count(newc)) {flag=1;break;}
            }
        }
        if(flag) continue;
        a[cur]=i;
        vis[newx][newy]=1;
        dfs(a,cur+1,i,node(newx,newy));
        vis[newx][newy]=0;
    }
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(vis,0,sizeof(vis));
        int k;
        scanf("%d%d",&n,&k);
        int x,y;
        for(int i=0;i<k;++i){
            scanf("%d%d",&x,&y);
            u.insert(node(x+150,y+150)); //障碍物坐标保存
        }
        cnt=0;
        int a[25];
        dfs(a,0,4,node(150,150));
        printf("Found %d golygon(s).\n\n",cnt);
        u.clear();
    }
    return 0;
}

用数组的AC代码：

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=300;
int dx[]={1,0,0,-1,5};
int dy[]={0,1,-1,0,5}; //east,north,south,west
char dir[]="ensw";
int vis[maxn][maxn],def[maxn][maxn];
int n,cnt;
struct node{
    int x,y;
    node(int x=0,int y=0):x(x),y(y){}
    bool operator < (const node &p) const{
        return x>p.x||(x==p.x&&y>p.y);
    }
};

void dfs(int *a,int cur,int d,node pos){
    if(cur==n&&pos.x==150&&pos.y==150){
        cnt++;
        for(int i=0;i<n;++i) printf("%c",dir[a[i]]);
        printf("\n");
        return;
    }
    if(cur>=n) return;
    if((abs(pos.x-150)+abs(pos.y-150))>((n-cur)*(n+cur+1)/2)) return; //cut
    for(int i=0;i<4;++i){
        if(dx[i]==dx[d]||dy[i]==dy[d]) continue;
        int newx=pos.x+(cur+1)*dx[i],newy=pos.y+(cur+1)*dy[i];
        if(vis[newx][newy]) continue; //已经旅游过
        int flag=0,c,p;
        if(newx==pos.x){
            c=min(newy,pos.y),p=max(newy,pos.y);
            for(int k=c;k<=p;++k){
                node newc(newx,k);
                if(def[newx][k]) {flag=1;break;}
            }
        }
        else if(newy==pos.y){
            c=min(newx,pos.x),p=max(newx,pos.x);
            for(int k=c;k<=p;++k){
                node newc(k,newy);
                if(def[k][newy]) {flag=1;break;}
            }
        }
        if(flag) continue;
        a[cur]=i;
        vis[newx][newy]=1;
        dfs(a,cur+1,i,node(newx,newy));
        vis[newx][newy]=0;
    }
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(vis,0,sizeof(vis));
        memset(def,0,sizeof(def));
        int k;
        scanf("%d%d",&n,&k);
        int x,y;
        for(int i=0;i<k;++i){
            scanf("%d%d",&x,&y);
            def[x+150][y+150]=1;
        }
        cnt=0;
        int a[25];
        dfs(a,0,4,node(150,150));
        printf("Found %d golygon(s).\n\n",cnt);
    }
    return 0;
}

如有不当之处欢迎指出！

相关文章