UVa 225 - Golygons ( DFS, 回溯, 剪枝 )

题意

平面上有k个障碍点。从(0,0)点出发，第一次走1个单位，第二次走2个单位，……，第n次走n个单位，恰好回到(0,0)。要求只能沿着东南西北方向走，且每次必须转弯90°（不能沿着同一个方向继续走，也不能后退）。走出的图形可以自交，但不能经过障碍点

AC代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;
#define mst(a) memset(a, 0, sizeof(a));
const char tn[] = "ensw";
const int maxn = 105;
int n, k, num;
const int dir[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
int G[2*maxn][2*maxn], vis[2*maxn][2*maxn], r[maxn], sum[25];

void init()
{
    sum[0] = 0;
    for( int i = 1; i <= 20; i++ )
        sum[i] = sum[i-1] + i;
}

bool judge( int x, int y, int d ){  //剪枝
    int dis = abs(x-105)+abs(y-105);
    if(dis > sum[n]-sum[d]) return false;
    return true;
}

void dfs( int f, int d, int x, int y )
{
    if(d==n)
    {
        if( x != 105 || y != 105 )
            return;
        for( int i = 0; i < n; i++ )
            printf("%c",tn[r[i]]);
        printf("\n");
        num++;
        return;
    }
    for( int k = 0; k < 4; k++ ){
        if( k == f || k + f == 3 ) continue;   //不允许直走或后退
        int dx = x, dy = y;
        int flag = 1;
        for( int i = 1; i <= d+1; i++ ){
            dx += dir[k][0];
            dy += dir[k][1];
            if(G[dx][dy] || !judge(dx, dy, d)){
                flag = 0;
                break;
            }
        }
        if(flag && !vis[dx][dy]){
            vis[dx][dy] = 1;
            r[d] = k;
            dfs(k, d+1, dx, dy);
            vis[dx][dy] = 0;
        }
    }
    return;
}


int main()
{
    int T, a, b;
    init();
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n, &k);
        mst(G);
        mst(vis);
        while(k--){
            scanf("%d%d",&a,&b);
            a += 105, b += 105;
            if( a >= 0 && b >= 0 )
                G[a][b] = 1;
        }
        num = 0;
        dfs(-1, 0, 105, 105);
        printf("Found %d golygon(s).\n\n",num);
    }
    return 0;
}