225:Golygons

Golygons

回溯加剪枝。某个方向可走的条件是此方向上没有障碍物挡道，还有一点容易被忽视的就是不能落到之前到过的点上！！！最重要的剪枝就是每走一步就判断一下剩下的步数是否有可能回到原点，还有就是如果提前到达原点也要剪掉。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50 + 5;
int T, n, k, cnt2, tmp = 105;
int counts[maxn], path[maxn];
int G[400][400];
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};
char xd[] = "ensw";
int dir[][2] = {1, 2, 0, 3, 0, 3, 1, 2};
void DFS(int x, int y, int cnt){
    if(counts[n] - counts[cnt-1] < abs(x) + abs(y)) return; //不可能回到原点
    if(cnt == n+1){
        if(!x && !y){
            for(int i = 1; i < n; i++){
                printf("%c", xd[path[i]]);
            }
            printf("%c\n", xd[path[n]]);
            cnt2++;
        }
        return;
    }
    else{
        for(int i = 0; i < 2; i++){
            int d = dir[path[cnt-1]][i];
            int nx = x + dx[d]*cnt, ny = y + dy[d]*cnt;
            if(G[nx+tmp][ny+tmp]) continue; //新点位于障碍处或之前走过
            if(!nx && !ny && cnt < n) continue; //提前回到原点
            int ok = 1;
            if(d == 0 || d == 3){
                int maxx = max(nx, x), minx = min(nx, x);
                for(int i = minx; i <= maxx; i++){
                    if(G[i+tmp][y+tmp] == -1){ ok = 0; break; }
                }
            }else{
                int maxy = max(ny, y), miny = min(ny, y);
                for(int i = miny; i <= maxy; i++){
                    if(G[x+tmp][i+tmp] == -1){ ok = 0; break; }
                }
            }
            if(!ok) continue; //此方向上有障碍物走不通
            path[cnt] = d;
            G[nx+tmp][ny+tmp] = 1;
            DFS(nx, ny, cnt+1);
            G[nx+tmp][ny+tmp] = 0;
        }
    }
}

int main()
{
    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);
    for(int i = 1; i <= 20; i++){
        counts[i] = i;
        counts[i] += counts[i-1];
    }
    scanf("%d", &T);
    int a, b;
    while(T--){
        cnt2 = 0;
        memset(G, 0, sizeof(G));
        scanf("%d%d", &n, &k);
        for(int i = 0; i < k; i++){
            scanf("%d%d", &a, &b);
            G[a+tmp][b+tmp] = -1;
        }
        for(int i = 0; i < 4; i++){
            int nx = dx[i], ny = dy[i];
            if(G[nx+tmp][ny+tmp]) continue;
            path[1] = i;
            G[nx+tmp][ny+tmp] = 1;
            DFS(nx, ny, 2);
            G[nx+tmp][ny+tmp] = 0;
        }
        printf("Found %d golygon(s).\n\n", cnt2);
    }

    return 0;
}