题解 P1556 【幸福的路】

直接dfs，就是要判断一下方向，来的方向和去的方向相同要剪枝，而且要注意最后要回到原点。 因为判断方向要用很多次，所以可以写成一个函数。用ifelse的话会稍微长一点，所以我直接return x1==x2?int(y1>y2):int(x1>x2)+2; 如果觉得这样可读性较差（其实我完全不觉得）ifelse也很好实现 顺便说一下我之前用邻接表写的，代码很长，浪费空间，而且因为数据比较小STL反而慢..所以用邻接表还是要注意数据大小 突然发现那些1000用不上了..那是之前我写邻接表用的，懒得删了，就这样吧.. ``` #include <iostream> using namespace std; int x[20],y[20],n,ans; bool vis[20]; void dfs(int c,int d,int dep); int dir(int x1,int y1,int x2,int y2); int main() { int i; cin>>n; for (i=1;i<=n;++i) { cin>>x[i]>>y[i]; x[i]+=1000; y[i]+=1000; } x[0]=y[0]=1000; dfs(0,4,0); cout<<ans; return 0; } void dfs(int c,int d,int dep) { if (dep==n) { if ((x[c]==1000||y[c]==1000)&&dir(1000,1000,x[c],y[c])!=d) { ++ans; } return; } vis[c]=true; for (int i=1;i<=n;++i) { if (!vis[i]&&(x[i]==x[c]||y[i]==y[c])&&dir(x[i],y[i],x[c],y[c])!=d) { dfs(i,dir(x[i],y[i],x[c],y[c]),dep+1); } } vis[c]=false; } int dir(int x1,int y1,int x2,int y2) { return x1==x2?int(y1>y2):int(x1>x2)+2; } ```