UVa 225 黄金图形（回溯+剪枝）

题意：
平面上有k个障碍点，从（0,0）出发，第一次走1个单位，第二次走2个单位，...第n次走n个单位，最后恰好回到（n，n）。每次必须转弯90°。

思路：

首先要注意的是坐标有可能是负的，所以在这里我们可以障碍点的坐标值+105变成正值，原点也就变成了（105,105），为什么是加105呢？因为我们最多走20步，最远是310，所以如果大于了105，之后肯定就回不来了，所以只需要加上105就可以了。

然后就是各种剪枝了，比较重要的就是当前距离大于剩余可走距离时，之后不管怎么走，肯定是回不到原点了，此时剪枝。

 1 #include<iostream> 
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<string>
 5 using namespace std;
 6 
 7 const int maxn = 105;
 8 int n, k, cnt;
 9 const int dir[4][2] = { { 1, 0 }, { 0, 1 }, { 0, -1 }, { -1, 0 } };
10 const char dict[] = "ensw";
11 int G[2*maxn][2*maxn];
12 int vis[2*maxn][2*maxn];
13 int path[maxn];
14 int sum[25];
15 
16 void init()
17 {
18     //计算步数
19     sum[0] = 0;
20     for (int i = 1; i <= 20; i++)
21         sum[i] = sum[i - 1] + i;
22 }
23 
24 bool judge(int x, int y,int d)
25 {
26     int dis = abs(x - 105) + abs(y - 105);
27     if (dis > sum[n] - sum[d]) return false;
28     return true;
29 }
30 
31 void dfs(int f, int d, int x, int y)
32 {
33     if (d == n)
34     {
35         if (x!=105 || y!=105)  return;
36         for (int i = 0; i < n; i++)
37             printf("%c", dict[path[i]]);
38         printf("
");
39         cnt++;
40         return;
41     }
42 
43     for (int k = 0; k < 4; k++)
44     {
45         if (k == f || k + f == 3)  continue;
46         int dx = x;
47         int dy = y;
48         int flag = 1;
49         for (int i = 1; i <= d + 1; i++)
50         {
51             dx = dx + dir[k][0];
52             dy = dy + dir[k][1];
53             if (G[dx][dy]||!judge(dx,dy,d))    { flag = 0; break; }
54         }
55         if (flag && !vis[dx][dy])
56         {
57             vis[dx][dy] = 1;
58             path[d] = k;
59             dfs(k, d + 1, dx, dy);
60             vis[dx][dy] = 0;
61         }
62     }
63     return;
64 }
65 
66 int main()
67 {
68     //ios::sync_with_stdio(false);
69     //freopen("D:\txt.txt", "r", stdin);
70     int T;    
71     init();
72     scanf("%d", &T);
73     while (T--)
74     {
75         scanf("%d%d",&n, &k);
76         memset(G, 0, sizeof(G));
77         memset(vis, 0, sizeof(vis));
78         for (int i = 0; i < k; i++)
79         {
80             int a, b;
81             scanf("%d%d", &a, &b);
82             a += 105;
83             b += 105;
84             if (a>=0 && b>=0)  G[a][b] = 1;
85         }
86         cnt = 0;
87         dfs(-1, 0, 105, 105);
88         printf("Found %d golygon(s).

", cnt);
89     }
90 }