题解 P1515 【旅行】

ZERORUSH · 2018-12-13 19:20:51 · 题解

被机房某位大佬拉了过来点题解的赞，然后就开始做这道题。。。

思路：将所有旅馆的位置都塞进数组里然后不撞南墙不回头

解释都在代码注释里

#include<iostream>
using namespace std;
int a,b,n,ans,x[40]={0,990,1010,1970,2030,2940,3060,3930,4060,4970,5030,5990,6010,7000},book[40];//初始化，没有book会死循环 
void dfs(int km)//深搜就完事了 
{
    for(int i=1;i<=n+13;i++)
    {
        if(x[i]>=km+a&&x[i]<=km+b&&book[i]==0)//在最短距离和最长距离之间就行了 
        {
            if(x[i]==7000)//到达目的地就+1； 
            {
                ans++;
                return;
            }
            book[i]=1;
            dfs(x[i]);
            book[i]=0;
        }
        else if(km+a>=7000)//最短距离可以到达目的地就+1 
        {
            ans++;
            return;
        }
    }
    return;
}
int main()//简单的主函数 
{
    cin>>a>>b>>n;
    for(int i=13;i<=n+12;i++) cin>>x[i];
    dfs(0);//从0开始 
    cout<<ans;
    return 0;
}

最后，我想说，我没有点赞（滑稽保命）

蒟蒻题解，不喜勿喷

更新：2018-12-25：dfs函数中的i<=n+14中的14改为13，感谢编程受害者 的指正

2019-2-20：main函数中的for(int i=13；i<=n+12；i++)改为for(int i=14;i<=n+13;i++),苍糜 的指正（已证明会影响AC）