题解 AT3875 【[ARC089A] Traveling】

有生之年居然能够入门题WA，果然我太菜了

好，进入正题：

一开始我看到这样的题目，第一反应就是万能的dfs！

思路：搜索路线，由于求最短时间所以可以直接剪枝向左和向上。而求出最短时间比较即可。

代码分数：0

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[41][101],t,fl;
int flag=0;
//bool f[41][41];
int minn=1e9;
void dfs(int x,int y,int sum)//dfs
{
    if(x<1||x>n||y<1||y>m) return;
    if(x==n&&y==m) minn=min(minn,sum);
    dfs(x+1,y,sum+1);
    dfs(x,y+1,sum+1);
}
int main()
{
	//ios::sync_with_stdio(false);
	int i,j;
	cin>>t;
    while(t--)
    {
        minn=1e9;
        cin>>fl>>n>>m;
        dfs(1,1,0);
        if(minn>fl||minn==0) flag=1;
        //cout<<minn<<" "<<flag<<endl;
        //else cout<<"No";
        //cout<<endl;
    }
    if(flag) cout<<"No";
    else cout<<"Yes";
	//dfs(1,1,a[1][1]);
	//cout<<maxx;
    //system("pause");
	return 0;
}

反思原因：求的是时间t时能否到达，而不是在时间t之前能否到达。

所以让我们再回过头来看看这道题，可以明显地发现其实所需时间就是x+y嘛！等等，还没完：时间大小判断了，那怎么知道t的时候到底能不能到达目的地呢？

经过模拟，可以清楚地发现：如果你要在t时间到达的话，最短时间到目的地后，可以不停地往回走一格再走回来，往回走一格再走回来......

所以，可以发现，只要剩余的时间mod2余数为0的时候，结果就一定能够到达！

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,t,fl;
int flag=0;
//bool f[41][41];
int minn=1e9;
void dfs(int x,int y,int sum)
{
    if(sum>minn) return;
    if(x<1||x>n||y<1||y>m) return;
    if(x==n&&y==m) minn=min(minn,sum);
    dfs(x+1,y,sum+1);
    dfs(x,y+1,sum+1);
}
int main()
{
	//ios::sync_with_stdio(false);
	int i,j;
	cin>>t;
    while(t--)
    {
        cin>>fl>>n>>m;
        if(n+m>fl) //时间太短，原地升天
        {
            flag=1;
            break;
        }
        if((fl-n-m)%2==1) //走了不回，原地升天
        {
            flag=1;
            break;//只要不行，直接走也
        }
    }
    if(flag) cout<<"No";
    else cout<<"Yes";
	//dfs(1,1,a[1][1]);
	//cout<<maxx;
    //system("pause");
	retun 0; //防止抄袭，抵抗之间
}

完结撒花~