UVa 225 – Golygons [DFS+剪枝]

距离100题还有4道，此时最忌讳急于求成，所以打算做题不看题解，有时候一道题很难需要想很多甚至做好几天都不能AC，但正是自己不断修改错误，优化代码，才使得自己的编程水平有进步，最后的AC才更加有成就感。

这道题思路还算简单，但是需要加各种剪枝条件，如当前做到达的地方能否再走n-d步到达原点，我感觉像是A*算法，提前估计当前状态还需要扩展几层才能得到目标状态。

经历了三次TLE，总结一下优化手段：

1.关闭输入输出缓冲同步，实现cin和cout跟scanf和printf几乎相同的速度，即加入代码：

1	ios::sync_with_stdio(false);

2.去掉所有STL存储的东西，能用数组存储的就用数组存，并且会发现有些时候数组操作起来更加方便，特别是DFS。

3.数组内查找某个元素是否存在，理论上find要比count快。

4.其他就是根据题目加各种剪枝了。

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
 
struct dot{
    int x, y;
    dot(int x = 0, int y = 0) : x(x), y(y) {}
    bool operator == (const dot & rhs) const{
        return x == rhs.x && y == rhs.y;
    }
};
int n, k, cnt = 0;
const int dir[4][2] = { { 1, 0 }, { 0, 1 }, { 0, -1 }, { -1, 0 } };  //东 北 南 西
const char dict[4] = { 'e', 'n', 's', 'w' };
int note[1024];
dot block[64], vis[1024];
 
void DFS(int curdir, int d, int x, int y)
{
    if (d == n){
        if (x || y) return;
        for (int i = 0; i < n; ++i)
            printf("%c", dict[note[i]]);
        printf("
"); ++cnt; return;
    }
    for (int i = 0; i < 4; ++i){
        if ((i == 0 || i == 3) && (curdir == 0 || curdir == 3)) continue;
        if ((i == 1 || i == 2) && (curdir == 1 || curdir == 2)) continue;
        dot v(x, y);
        if ((n - d - 1)*n < abs(v.x + (d + 1)*dir[i][0]) + abs(v.y + (d + 1)*dir[i][1]))
            goto loop;
        for (int j = 0; j < d + 1; ++j){
            v.x += dir[i][0];
            v.y += dir[i][1];
            if (find(block, block + k, v) != block + k)
                goto loop;
        }
        if (find(vis, vis + d, v) == vis + d){
            vis[d] = v; note[d] = i;
            DFS(i, d + 1, v.x, v.y);
        }
    loop:;
    }
}
void init()
{
    cnt = 0;
    memset(vis, 0, sizeof(vis));
    memset(block, 0, sizeof(block));
    memset(note, 0, sizeof(note));
}
int main()
{
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (init(), T--){
        cin >> n >> k;
        for (int i = 0; i < k; ++i){
            dot t; cin >> t.x >> t.y;
            block[i] = t;
        }
        DFS(-1, 0, 0, 0);
        printf("Found %d golygon(s).

", cnt);
    }
    return 0;
}