[UVa]225.cpp

[UVa]225 - Golygons.cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;

const int maxn = 250;
const int dx[] = {1, 0, 0, -1}, dy[] = {0, 1, -1, 0};
const char dire[] = {'e', 'n', 's', 'w'};
struct pos{
    int x, y;
    pos(int _x, int _y):x(_x),y(_y){}
};

int dep, ans = 0;
string s;
vector<pos> block;
bool vis[maxn][maxn][4];

bool illegal(int p, int k){
    if(p == 0 || p == 3)return k == 0 || k == 3;
    else if(p == 1 || p == 2)return k == 1 || k == 2;
    else return false;
}
bool check(int x, int y, int nx, int ny){
    for(int i = 0; i < block.size(); i++){
        int bx = block[i].x, by = block[i].y;
        //printf("%d %d %d %d %d %d\n", bx, by, x, y, nx, ny);
        if(x == bx && nx == bx)
            if((y <= by && ny >= by) || (ny <= by && y >= by))return true;
        if(y == by && ny == by)
            if((x <= bx && nx >= bx) || (nx <= bx && x >= bx))return true;
    }
    return false;
}
void dfs(int cx, int cy,int cd, int pre){
    if(cd == dep + 1){
        if(cx == cy && cx == 0){
            printf("%s\n", s.c_str());
            ans++;
        }
        return;
    }
    for(int i = 0; i < 4; i++){
        int xx = cx + cd * dx[i], yy = cy + cd * dy[i], p = 0;
        int uxx = abs(xx), uyy = abs(yy);

        if(xx < 0 && yy < 0) p = 0;
        else if(xx < 0 && yy > 0) p = 1;
        else if(xx > 0 && yy < 0) p = 2;
        else if(xx >= 0 && yy >= 0)p = 3;

        if(illegal(pre, i))continue;
        if(check(cx, cy, xx, yy))continue;
        if(vis[uxx][uyy][p])continue;

        vis[uxx][uyy][p] = true;
        s.push_back(dire[i]);
        dfs(xx, yy, cd + 1, i);
        vis[uxx][uyy][p] = false;
        s.resize(s.size()-1);
    }
}
int main(){
    int kase, x, y, t;
    scanf("%d", &kase);
    while(kase--){
        ans = 0;
        block.clear();s = "";
        memset(vis, false, sizeof(vis));

        scanf("%d", &dep);
        scanf("%d", &t);
        for(int i = 0; i < t; i++){
            scanf("%d%d", &x, &y);
            block.push_back(pos(x, y));
        }
        dfs(0, 0, 1, -1);
        printf("Found %d golygon(s).\n\n", ans);
    }
}