- /*
- 没什么难点,就几个细节需要注意一下
- 一个是dfs时需要记录下上一次改变的方向
- 第二个是千万不要忘了最后要返回(0,0)
- */
- #include<iostream>
- #include<cstdio>
- #define maxn 11
- using namespace std;
- int n,ans;
- bool vis[maxn];
- struct node{
- int x,y;
- }a[maxn];
- void dfs(int x,int y,int cnt,int pre){//pre:1上,2下,3左,4右
- if(cnt==n){
- if(x==0&&y>0&&pre!=2){ans++;return;}
- if(x==0&&y<0&&pre!=1){ans++;return;}
- if(y==0&&x>0&&pre!=3){ans++;return;}
- if(y==0&&x<0&&pre!=4){ans++;return;}
- }
- for(int i=1;i<=n;i++){
- if(vis[i])continue;
- if(a[i].x>x&&a[i].y==y&&pre!=4){//正右方
- vis[i]=1;
- dfs(a[i].x,a[i].y,cnt+1,4);
- vis[i]=0;
- }
- if(a[i].x<x&&a[i].y==y&&pre!=3){//正左方
- vis[i]=1;
- dfs(a[i].x,a[i].y,cnt+1,3);
- vis[i]=0;
- }
- if(a[i].x==x&&a[i].y<y&&pre!=2){//正下方
- vis[i]=1;
- dfs(a[i].x,a[i].y,cnt+1,2);
- vis[i]=0;
- }
- if(a[i].x==x&&a[i].y>y&&pre!=1){//正上方
- vis[i]=1;
- dfs(a[i].x,a[i].y,cnt+1,1);
- vis[i]=0;
- }
- }
- }
- int main(){
- //freopen("Cola.txt","r",stdin);
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- scanf("%d%d",&a[i].x,&a[i].y);
- dfs(0,0,0,0);
- cout<<ans;
- }
来源: http://www.bubuko.com/infodetail-2306431.html