【搜索】UVa225 —— Golygons

题目传送门

水啊水啊…

可以直接暴力,判断是否经过障碍也可以暴力判断,注意搜索的顺序按照字典序最小即可.
另注意一个可行性剪枝,即判断当前的位置能否在之后的步数中回到原点.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int L=100;
const int MAXN=25;
const int MAXM=205;

int n,m,sum;
int ban[MAXM][MAXM],vis[MAXM][MAXM];
char ans[MAXN];
const char ch[2][2]={{'e','w'},{'n','s'}};
const int f[2][2][2]={{{1,0},{-1,0}},{{0,1},{0,-1}}};

bool check(int x,int y,int op,int d,int len){
    for(int i=1;i<=len;i++){
        x=x+f[op][d][0];
        y=y+f[op][d][1];
        if(ban[x][y]) return 0;
    }
    return 1;
}

void dfs(int len,int x,int y,int op){
    if(len==n+1){
        if(x!=L||y!=L) return;
        printf("%s\n",ans+1);
        sum++;
        return;
    }
    if(abs(x-L)+abs(y-L)>(n-len+1)*(len+n)/2) return;
    for(int i=0;i<2;i++){
        int nx=x+len*f[op][i][0];
        int ny=y+len*f[op][i][1];
        if((len^n&&nx==L&&ny==L)||nx<0||ny<0||nx>2*L||ny>2*L||vis[nx][ny]||!check(x,y,op,i,len)) continue;
        ans[len]=ch[op][i];
        vis[nx][ny]=1;
        dfs(len+1,nx,ny,op^1);
        vis[nx][ny]=0;
        ans[len]='\0';
    }
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(ban,0,sizeof ban);
        sum=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int x,y; scanf("%d%d",&x,&y);
            if(abs(x)>L||abs(y)>L) continue;
            ban[x+L][y+L]=1;
        }
        if(!ban[L+1][L]) ans[1]='e',vis[L+1][L]=1,dfs(2,L+1,L,1),vis[L+1][L]=0;
        if(!ban[L][L+1]) ans[1]='n',vis[L][L+1]=1,dfs(2,L,L+1,0),vis[L][L+1]=0;
        if(!ban[L][L-1]) ans[1]='s',vis[L][L-1]=1,dfs(2,L,L-1,0),vis[L][L-1]=0;
        if(!ban[L-1][L]) ans[1]='w',vis[L-1][L]=1,dfs(2,L-1,L,1),vis[L-1][L]=0;
        printf("Found %d golygon(s).\n\n",sum);
    }
}