P9107 [PA2020] Wycieczka górska 题解

_•́へ•́╬_ · 2023-03-03 23:45:32 · 题解

思路

诈骗。所有人走的路径一定都是一样的。bfs 搜出来即可。

给人看的思路

首先，如果没有向上走，那么会向下走 n-1 次。

考虑在整个过程中向上走了 x 次。那么，就要额外向下走 x 次，也就是一共向下走 x+n-1 次。酱紫最后才能到达最后一行。

向左向右同理。

把向上和向左的次数加起来记作 a，统称【向回走】。

那么，会【向前走】 n-1+m-1+a 次。

搜出使 a 最小的路径。

code

#include<stdio.h>
#include<deque>
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,p,ans[2333][2333];long long ans1=1ll<<60,ans2;char s[2333][2333];
struct node
{
    int x,y,a;
    inline node(const int&x,const int&y,const int&a):x(x),y(y),a(a){}
};deque<node>q;
main()
{
    read(n);read(m);read(p);
    for(int i=0;i<n;++i)for(int j=0;j<m;s[i][j]^='X',ans[i][j++]=1<<30)
        for(;s[i][j]=nc(),(s[i][j]^'.')&&(s[i][j]^'X'););
    ans[0][0]=0;q.emplace_back(0,0,0);
    for(node i(0,0,0);q.size();)
    {
        i=q.front();q.pop_front();
        if(ans[i.x][i.y]^i.a)continue;
        if(i.x&&s[i.x-1][i.y]&&ans[i.x-1][i.y]>i.a+1)
            q.emplace_back(i.x-1,i.y,ans[i.x-1][i.y]=i.a+1);
        if(i.y&&s[i.x][i.y-1]&&ans[i.x][i.y-1]>i.a+1)
            q.emplace_back(i.x,i.y-1,ans[i.x][i.y-1]=i.a+1);
        if(i.x<n-1&&s[i.x+1][i.y]&&ans[i.x+1][i.y]>i.a)
            q.emplace_front(i.x+1,i.y,ans[i.x+1][i.y]=i.a);
        if(i.y<m-1&&s[i.x][i.y+1]&&ans[i.x][i.y+1]>i.a)
            q.emplace_front(i.x,i.y+1,ans[i.x][i.y+1]=i.a);
    }
    for(int x,y;p--;)
    {
        read(x);read(y);
        long long qwq=x*(long long)(n-1+m-1+ans[n-1][m-1])+
            y*(long long)(ans[n-1][m-1]);
        if(qwq<ans1)ans1=qwq,ans2=0;
        if(qwq==ans1)++ans2;
    }
    printf("%lld %lld",ans1,ans2);
}