Golygons UVA - 225

对障碍物以及未访问点、已经访问的点分开标记，同时注意将所有的点都进行平移，这样可以更好地处理坐标为负数地情况。同时，如果从当前的点回到原点的距离已经超过了能够走的路径的总长度，那么就不需要再次进行后续搜索了，直接剪枝，提高效率。

#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<deque>
using namespace std;

int T;
int sumSteps[25];
int n, k,total;
int dis = 105;
int area[250][250];
const char directions[] = "ensw";
int dx[] = {1,0,0,-1};
int dy[] = {0,1,-1,0};
int path[250];

void Init(){
	total = 0;
	cin >> n >> k;
	memset(area,0,sizeof(area));
	for (int i = 0; i < k; i++){
		int a, b;
		cin >> a >> b;
		if (abs(a) > dis || abs(b) > dis) continue;
		area[a + dis][b + dis] = -1;
	}
}

bool feasible(int x,int y,int i,int k){//k代表该方向上的步数，i代表相应的方向
	if (abs(x) + abs(y) > sumSteps[n] - sumSteps[k-1]) return false;
	for (int t = 1; t <= k; t++){
		int newx = x + dx[i]*t;
		int newy = y + dy[i] * t;
		if (abs(newx) > dis || abs(newy) > dis) return false;
		if (area[newx+dis][newy+dis] == -1) return false;
	}
	return true;
}

void Solve(int cur_n,int curx,int cury,int d){
	if (cur_n > n){
		if (curx == 0 && cury == 0){
			for (int i = 1; i <= n; i++) cout << directions[path[i]];
			cout << endl;
			total++;
		}
		return;
	}
	for (int i = 0; i < 4; i++){
		path[cur_n] = i;
		if (i == d || i + d == 3) continue;
		if (!feasible(curx, cury, i, cur_n)) continue;
		int newx = curx + dx[i] * cur_n, newy = cury + dy[i] * cur_n;
		if (area[newx+dis][newy+dis] != 0) continue;
		area[newx+dis][newy+dis] = 1;
		Solve(cur_n + 1, newx, newy, i);
		area[newx+dis][newy+dis] = 0;
	}
}

int main(){
	cin >> T;
	sumSteps[0] = 0;
	for (int i = 1; i <= 20; i++) sumSteps[i] = sumSteps[i - 1] + i;
	while (T--){
		Init();
		Solve(1, 0, 0, -1);
		cout << "Found "<<total<<" golygon(s)."<< endl << endl;
	}
	return 0;
}