題目：Golygons

題意：平面上有k個(gè)障礙點(diǎn)。 從(0,0)點(diǎn)出發(fā)，第一次走1個(gè)單位，第二次走2個(gè)單位，……，第n次走n個(gè)單位，恰好回到(0,0)。 要求只能沿著東南西北方向走，且每次必須轉(zhuǎn)彎90°（不能沿著同一個(gè)方向繼續(xù)走，也不能后退）。 走出的圖形可以自交，但不能經(jīng)過障礙點(diǎn)。輸出所有可走的方向路徑序列。

思路：標(biāo)準(zhǔn)dfs回溯。。。開始用pair和map解決負(fù)坐標(biāo)問題，可老是TLE，最后參考了網(wǎng)上的把代碼都向上平移了100個(gè)距離。

（1）輸出：將所有障礙點(diǎn)加上100，超出地圖范圍的不要！

（2）枚舉：從原點(diǎn)開始枚舉4個(gè)方向，除了原點(diǎn)4個(gè)方向都可以走外，其他點(diǎn)都是根據(jù)上一個(gè)點(diǎn)的方向后，排除當(dāng)前不能走的后剩下的繼續(xù)遞歸。

（3）判斷：枚舉每個(gè)點(diǎn)時(shí)預(yù)先將上點(diǎn)坐標(biāo)和本次的走的步數(shù)和方向進(jìn)行查找此過程時(shí)候出現(xiàn)障礙物，出現(xiàn)則不走，否則走。

（4）剪枝：預(yù)先打步數(shù)表，sum[n]代表第n次最多走幾步，如果當(dāng)前坐標(biāo)到原點(diǎn)的距離（|x|+|y|） 大于 最多還能走的步數(shù)（sum[20] - sum[k]） 即可剪枝！

參考：JeraKrs博客

代碼：

#include <iostream>#include <cstdio>#include <algorithm>#include <map>#include <cstring>using namespace std;const int maxn = 250;const int expand = 100;//typedef pair<int,int> coor;//map<coor,int>g;int g[maxn][maxn];int n,path[maxn],ans;char dir[] = {"ensw"};int dx[] = {1,0,0,-1};int dy[] = {0,1,-1,0};int sum[21];inline bool exceed(int x,int y){//超出地圖范圍    if(abs(x)+expand > maxn || abs(y)+expand > maxn) return true;    return false;}inline bool judge(int x,int y,int st,int d){//判斷走的過程是否穿越障礙物    for(int i=0;i<st;i++){        x += dx[d]; y += dy[d];        if(exceed(x,y)) continue;        if(g[x+expand][y+expand] == -1) return false;    }    return true;}void dfs(int x,int y,int steps,int PRev){    if(abs(x) + abs(y) > sum[20] - sum[steps]) return;//剪枝：當(dāng)前位置到原點(diǎn)距離非常大直接退出    if(steps > n){        if(x == 0 && y == 0){            for(int i=1;i<steps;i++) printf("%c",dir[path[i]]);printf("/n");            ans++;        }        return;    }    //int prev = path[steps-1];    for(int i=0;i<4;i++){       if(i == prev || i+prev == 3) continue;//排除直走和后退       int tx = x + steps*dx[i] , ty = y + steps*dy[i];       if(judge(x,y,steps,i) && !g[expand+tx][expand+ty]){            path[steps] = i;//保存方向            g[expand+tx][expand+ty] = 1;            dfs(tx,ty,steps+1,i);            g[expand+tx][expand+ty] = 0;       }    }}int main(){    int t,k,u,v;    for(int i=1;i<=20;i++) sum[i] = sum[i-1] + i;//將所有步數(shù)打表用于剪枝    scanf("%d",&t);    while(t--){        scanf("%d%d",&n,&k);        memset(g,0,sizeof(g));        for(int i=0;i<k;i++){            scanf("%d%d",&u,&v);            if(exceed(u,v)) continue;            g[u+expand][v+expand] = -1;        }        path[0] = -3;        ans = 0;        dfs(0,0,1,-3);        printf("Found %d golygon(s)./n/n",ans);    }    return 0;}