UVA - 225 Golygons

提莫链接：UVA - 225 

题意：

从（0,0）点出发，第一次走一步，第二次走两步，第三次走三步......第n次走n步。有k个障碍点的坐标，不能路过障碍点。每走一次参观一个城市，同一个城市不能参观两次，但可以路过。求有多少条路径可以走n次后返回到0,0点。按字典序输出路径。

思路：

暴力深搜。只需注意一下障碍点和城市的标记，方向的设置顺序即可。

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
using namespace std;
int n,m,cnt;
char path[40];
int ff[4][2]={0,1, 1,0, -1,0, 0,-1};//ensw
int vis[800][800];
int check(int y,int x,int fx,int step)
{
    if(abs(y-400)+abs(x-400)>(n+step)*(n-step+1)/2) return 0;//剪枝
    for(int i=0;i<step;i++)
    {
        y+=ff[fx][0];
        x+=ff[fx][1];
        if(vis[y][x]==-1) return 0;
    }
    return 1;
}
void dfs(int y,int x,int step,int fx)
{
    if(step==n && y==400 && x==400)
    {
        path[step]=0;
        puts(path);
        cnt++;
        return;
    }
    if(step>=n) return;
    for(int i=0;i<4;i++)
    {
        int ty=y+ff[i][0]*(step+1);
        int tx=x+ff[i][1]*(step+1);
        if(vis[ty][tx] || fx+i==3 || fx==i || !check(y,x,i,step+1))
            continue;
        vis[ty][tx]=1;
        switch(i)
        {
            case 0: path[step]='e'; break;
            case 1: path[step]='n'; break;
            case 2: path[step]='s'; break;
            case 3: path[step]='w'; break;
        }
        dfs(ty,tx,step+1,i);
        vis[ty][tx]=0;
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        int xx,yy;
        memset(vis,0,sizeof vis);
        cnt=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&xx,&yy);
            vis[yy+400][xx+400]=-1;
        }
        dfs(400,400,0,-1);
        printf("Found %d golygon(s).\n\n",cnt);
    }
    return 0;
}