# 题意：在一个坐标系的原点出发走 k 步回到原点，第 i 步走 i 个单位长度。有 x 个障碍，障碍不能经过或者停留。每一步结束的地方不能再作为结束的地方。求有多少中方案以及每个方案的移动序列（用 wsne 表示），按字典序输出。

### 剪枝：如果当前距离原点的距离大于以后可以走的总距离，则停止继续搜索。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define MC 251

using namespace std;

int maxl,block;
short mp[MC][MC];
int T;
short nxt[5][3]= {{0,0,0},{0,1,0},{0,0,1},{0,0,-1},{0,-1,0}};
char dir[6]="hensw",route[100];
int ansnum;

typedef struct p
{
int x,y;
} pot;
pot targ;

int input()
{
int a,b;
memset(mp,0,sizeof(mp));
scanf("%d%d",&maxl,&block);
for(int i=1; i<=block; i++)
{
scanf("%d%d",&a,&b);
mp[a+MC][b+MC]=1;
}
return maxl;
}

int dist(pot a,pot b)
{
return abs(a.x-b.x)+abs(a.y-b.y);
}

int trymove(pot from,pot to)
{
if(from.x==to.x)
{
for(int i=min(from.y,to.y)+MC; i<=max(from.y,to.y)+MC; i++)
if(mp[from.x+MC][i]==1)
return 0;
if(mp[to.x+MC][to.y+MC]==2)return 0;
}
else
{
for(int i=min(from.x,to.x)+MC; i<=max(from.x,to.x)+MC; i++)
if(mp[i][from.y+MC]==1)
return 0;
if(mp[to.x+MC][to.y+MC]==2)return 0;
}
return 1;
}

void sch(int d,int last,pot now)
{
pot next;
if(now.x==targ.x&&now.y==targ.y&&d==maxl)
{
printf("%s\n",route);
ansnum++;
return;
}
if((maxl-d)*(d+1+maxl)/2<dist(now,targ))return;
for(int i=1; i<=4; i++)
{
if(i!=last&&i!=5-last)
{
next.x=now.x+nxt[i][1]*(d+1);
next.y=now.y+nxt[i][2]*(d+1);
if(trymove(now,next))
{
mp[next.x+MC][next.y+MC]=2,route[d]=dir[i];
sch(d+1,i,next);
mp[next.x+MC][next.y+MC]=0;
}
}
}
}

int main()
{
pot start;
scanf("%d",&T);
for(int i=1; i<=T; i++)
{
input();
ansnum=0,targ.x=0,targ.y=0,start.x=0,start.y=0;
memset(route,0,sizeof(route));
sch(0,0,start);
printf("Found %d golygon(s).\n\n",ansnum);
}
return 0;
}


# 优化后代码↓

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define MC 251

using namespace std;

int maxl,block;
short mp[MC*2][MC*2],xqzh[MC*2][MC*2],yqzh[MC*2][MC*2];
int T;
short nxt[5][3]= {{0,0,0},{0,1,0},{0,0,1},{0,0,-1},{0,-1,0}};
char dir[6]="hensw",route[100];
int ansnum;

typedef struct p
{
int x,y;
} pot;
pot targ;

int input()
{
int a,b;
memset(mp,0,sizeof(mp));
scanf("%d%d",&maxl,&block);
for(int i=1; i<=block; i++)
{
scanf("%d%d",&a,&b);
mp[a+MC][b+MC]=1;
}
for(int i=1;i<=MC*2-1;i++)
for(int j=1;j<=MC*2-1;j++)
xqzh[i][j]=xqzh[i][j-1]+mp[i][j],yqzh[j][i]=yqzh[j][i-1]+mp[i][j];
return maxl;
}

int dist(pot a,pot b)
{
return abs(a.x-b.x)+abs(a.y-b.y);
}

int trymove(pot from,pot to)
{
int l,r;
if(from.x==to.x)
{
l=min(to.y,from.y),r=to.y+from.y-l;
if(xqzh[to.x+MC][l-1+MC]!=xqzh[from.x+MC][r+MC]||mp[to.x+MC][to.y+MC]==2)return 0;
}
else
{
l=min(to.x,from.x),r=to.x+from.x-l;
if(yqzh[to.y+MC][l-1+MC]!=yqzh[from.y+MC][r+MC]||mp[to.x+MC][to.y+MC]==2)return 0;
}
return 1;
}

void sch(int d,int last,pot now)
{
pot next;
if(now.x==targ.x&&now.y==targ.y&&d==maxl)
{
printf("%s\n",route);
ansnum++;
return;
}
if((maxl-d)*(d+1+maxl)/2<dist(now,targ))return;
for(int i=1; i<=4; i++)
{
if(i!=last&&i!=5-last)
{
next.x=now.x+nxt[i][1]*(d+1),next.y=now.y+nxt[i][2]*(d+1);
if(trymove(now,next))
{
mp[next.x+MC][next.y+MC]=2;
route[d]=dir[i];
sch(d+1,i,next);
mp[next.x+MC][next.y+MC]=0;
}
}
}
}

int main()
{
pot start;
scanf("%d",&T);
for(int i=1; i<=T; i++)
{
input();
ansnum=0,targ.x=0,targ.y=0,start.x=0,start.y=0;
memset(route,0,sizeof(route));
sch(0,0,start);
printf("Found %d golygon(s).\n\n",ansnum);
}
return 0;
}