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

Uva 225 Golygons

程序员文章站 2024-03-19 08:51:16
...

  这道题如果直接用Dfs,运气好的话是可以直接过的。

  但如果要在Dfs的基础上加快速度,剪枝是必不可少的。

  我的剪枝策略

    1.当前点(x,y)回到出发点至少需要 |x| +| y| 步,如果剩余的步数不足以达到当前所需的最小步数,则剪枝。比如在没有障碍的情况下,要求在4次行走时完成回路,如果第三次走到(2,4),那么计算得要回到出发点最少需要5步,但此时剩余4步,不可能走回出发点,因此可以剪枝。

    2.如果当前 x 或 y 的值,超过了所能走的步数的一半,则剪枝

    3.如果没有在最后一步就走到出发点,就剪枝。比如在没有障碍的情况下,要求在20次行走时完成回路,那么就很容易在第8次的时候就走回出发点(题目中的例子就是8次回到出发点),此时已经没有继续走第9次,因此可以剪枝。

  需要额外注意的一点是,此题中的x,y坐标是直角坐标系的坐标,而不是矩阵的坐标。

  

// #include <iostream>
// #include <cstring>
// #include <cstdio>
// #include <algorithm>
// #include <vector>
#include <bits/stdc++.h>

using namespace std;

struct Point{
    int x, y;
    Point(){}
    Point(int a, int b){
        x = a; y = b;
    }
};
vector<Point> point;
int dirPath[30];
int dir[4][2] = {1, 0, 0, 1, 0, -1, -1, 0};
int revDir[4] = {3, 2, 1, 0};
char dirChar[10] = "ensw";
int N, K, C;

void Read() {
    scanf("%d%d", &N, &K);
    point.clear();
    int x, y;
    for(int i=0; i<K; ++ i) {
        scanf("%d%d", &x, &y);
        point.push_back(Point(x, y));
    }
}

const int MAXN = 600;
const int OFFSET = 256;
bool vis[MAXN][MAXN];
bool IsVis(const Point &p) {
    return vis[p.x+OFFSET][p.y+OFFSET];
}

void SetVis(const Point &p, bool flag) {
    vis[p.x+OFFSET][p.y+OFFSET] = flag;
}

bool CanPut(const Point& p1, const Point& p2) {
    if(p1.x == p2.x) {
        for(size_t i = 0; i < point.size(); ++ i) {
            if(point[i].x == p1.x && point[i].y >= p1.y && point[i].y <= p2.y) {
                return false;
            }else if(point[i].x == p1.x && point[i].y >= p2.y && point[i].y <= p1.y) {
                return false;
            }
        }
    } else if(p1.y == p2.y) {
        for(size_t i = 0; i < point.size(); ++ i) {
            if(point[i].y == p1.y && point[i].x >= p1.x && point[i].x <= p2.x) {
                return false;
            }else if(point[i].y == p1.y && point[i].x >= p2.x && point[i].x <= p1.x) {
                return false;
            }
        }
    }
    return true;
}

void Print() {
    for(int i=1; i<N+1; i++) {
        printf("%c", dirChar[dirPath[i]]);
    }
    printf("\n");
}

void Dfs(Point p, int key) {
    if(abs(p.x) + abs(p.y) > (key+N) * (N-key+1) >> 1) {
        return ;
    }
    if(abs(p.x) > (1+N) * N >> 1 || abs(p.y) > (1+N) * N >> 1) {
        return ;
    }
    if(key == N + 1) {
        if(p.x == 0 && p.y == 0) {
            ++ C;
            Print();
        }
        return ;
    } else if(p.x == 0 && p.y == 0) {
        return ;
    }
    for(int i=0; i<4; i++) {
        if(dirPath[key - 1] != i && i != revDir[dirPath[key - 1]]) {
            Point next( p.x + key * dir[i][0], p.y + key * dir[i][1] );
            if(!IsVis(next) && CanPut(p, next)) {
                dirPath[key] = i;
                SetVis(next, true);
                Dfs(next, key+1);
                SetVis(next, false);
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    while(T --) {
        Read();
        memset(vis, false, sizeof(vis));
        Point start(0, 0);
        C = 0;
        for(int i=0; i<4; i++) {
            Point next( start.x+dir[i][0], start.y+dir[i][1] );
            if(CanPut(start, next)) {
                dirPath[1] = i;
                SetVis(next, true);
                Dfs(next, 2);
                SetVis(next, false);
            }
        }
        printf("Found %d golygon(s).\n", C);
        printf("\n");
    }
    return 0;
}