题目：
思路：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
int sum=0,g[1000010];
struct node{int x,y;
}a[1000010];
int f[1000010],v[1000010],n=0;
void dfs(int x,int v1){//x:搜到第几个,v1:上次的方向if(x==n+1){int d=0;if(a[f[x-1]].x<0)d=1;if(a[f[x-1]].x>0)d=2;if(a[f[x-1]].y<0)d=3;if(a[f[x-1]].y>0)d=4;if(v1!=d)g[f[x-1]]=1;//判断方向是否相同for(int i=1;i<=n;i++)if(!g[i]){if(v1!=d)g[f[x-1]]=0;return ;}if(v1!=d)g[f[x-1]]=0;if(a[f[x-1]].x==0 || a[f[x-1]].y==0){sum++;}return ;}for(int i=1;i<=n;i++){if(!v[i]){if(a[i].x==a[f[x-1]].x || a[i].y==a[f[x-1]].y){//是否在正东南西北方向int d=0;if(a[i].x>a[f[x-1]].x)d=1;if(a[i].x<a[f[x-1]].x)d=2;if(a[i].y>a[f[x-1]].y)d=3;if(a[i].y<a[f[x-1]].y)d=4;if(d!=v1)g[f[x-1]]=1;else if(x!=n) continue;//剪枝v[i]=1;f[x]=i;dfs(x+1,d);//接着搜索v[i]=0;if(d!=v1)g[f[x-1]]=0;}}}
}
int main(){int i,j,k,m;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);//输入}dfs(1,0);printf("%d\n",sum);//输出return 0;
}本文链接：https://my.lmcjl.com/post/15648.html
展开阅读全文
4 评论