欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-19 08:28:46
...

题意

平面上有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;
}