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

 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("\n");
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).\n\n", cnt);
89     }
90 }