ouuan 的博客

ouuan 的博客

题解 P1556 【幸福的路】

posted on 2018-02-06 11:03:27 | under 题解 |

直接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;
}