题意：从(0.0)点出发，第一次走一步……第k次走k步，且每次必须转90度，不能走重复的点。求k次后回到出发点的所有情况。按最小字典序从小到大输出。
思路：
把所有坐标+220，保证其是正数，然后搜索。
#include#include #include #include #include #include typedef long long ll;using namespace std;const int inf = 0x3f3f3f3f;int tx[100];int ty[100];int dir[4][2] = { {1,0},{0,1},{0,-1},{-1,0}};int vis[1000][1000];char dire[] = {"ensw"};int all;struct node{ int step; int x,y; int dir;};int n,k;int ans[200];bool judge(int i,node a) //判断是否能走{ int x = a.x+dir[i][0]*(a.step+1); int y = a.y+dir[i][1]*(a.step+1); if(i == 1 || i == 2) { for(int j = 0; j < k; j++) { if(tx[j] == x && ty[j] >= y && ty[j] <= a.y && i == 2) return true; if(tx[j] == x && ty[j] >= a.y && ty[j] <= y && i == 1) return true; } } if(i == 0 || i == 3) { for(int j = 0; j < k; j++) { if(ty[j] == y && tx[j] >= x && tx[j] <= a.x && i == 3) return true; if(ty[j] == y && tx[j] >= a.x && tx[j] <= x && i == 0) return true; } } return false;}void dfs(node a){ if(a.x == 220 && a.y == 220 && a.step == n) {// printf("%d\n",a.step);// for(int i = 0; i < a.step;i++)// printf("%d ",ans[i]);// printf("\n"); for(int i = 0; i < a.step; i++) { printf("%c",dire[ans[i]]); } printf("\n"); all++; return ; } if(a.step >= n) return; for(int i = 0; i < 4; i++) { if(i == 0 && (a.dir == 3||a.dir == 0))continue; if(i == 1 && (a.dir == 2||a.dir == 1))continue; if(i == 2 && (a.dir == 1||a.dir == 2))continue; if(i == 3 && (a.dir == 0||a.dir == 3))continue; if(judge(i,a)) continue; node tt = a; ans[a.step] = i; tt.x = a.x+dir[i][0]*(a.step+1); tt.y = a.y+dir[i][1]*(a.step+1); if(vis[tt.x][tt.y]) continue; vis[tt.x][tt.y] = 1; tt.dir = i; tt.step = a.step + 1; dfs(tt); vis[tt.x][tt.y] = 0; } return ;}int main(){ int cas = 1,T; int a,b; scanf("%d ",&T); while(T--) { scanf("%d %d ",&n,&k); memset(vis,0,sizeof(vis)); for(int i = 0; i < k; i++) { scanf("%d %d",&a,&b); tx[i] = a+220; ty[i] = b+220; } node cur; all = 0; cur.x = 220,cur.y = 220,cur.step = 0,cur.dir = -1; dfs(cur); printf("Found %d golygon(s).\n",all); printf("\n"); } return 0;}