题解：AT_abc258_f [ABC258F] Main Street

· · 题解

题目传送门

思路

怎么题解都差不多？

我们看了题目后显然有了思路，那么为什么这题是蓝？显然是因为细节原因。下面思路里会进行代码封装，简洁明了。

思路显然是分类 17 次，即起点上下左右，终点上下左右共 4 \times 4 =16 加上最开始直接走的 1 种，共 17 种。

下文简称上为 \text{u}，下为 \text{d}，左为 \text{l}，右为 \text{r}。

那么我们只需要把起点和终点的上下左右最近的大通道找出来即可。

显然有：

int su=sy/B*B,eu=ey/B*B;//up
int sd=su+B,ed=eu+B;//down
int sl=sx/B*B,el=ex/B*B;//left
int sr=sl+B,er=el+B;//right

s 前缀表示起点，e 前缀表示终点。

那么直接暴力枚举 16 种情况就行。

//up
ans=min(ans,dis(sx,su,ex,eu)+abs(sy-su)*K+abs(ey-eu)*K);
ans=min(ans,dis(sx,su,ex,ed)+abs(sy-su)*K+abs(ey-ed)*K);
ans=min(ans,dis(sx,su,el,ey)+abs(sy-su)*K+abs(ex-el)*K);
ans=min(ans,dis(sx,su,er,ey)+abs(sy-su)*K+abs(ex-er)*K);
//down
ans=min(ans,dis(sx,sd,ex,eu)+abs(sy-sd)*K+abs(ey-eu)*K);
ans=min(ans,dis(sx,sd,ex,ed)+abs(sy-sd)*K+abs(ey-ed)*K);
ans=min(ans,dis(sx,sd,el,ey)+abs(sy-sd)*K+abs(ex-el)*K);
ans=min(ans,dis(sx,sd,er,ey)+abs(sy-sd)*K+abs(ex-er)*K);
//left
ans=min(ans,dis(sl,sy,ex,eu)+abs(sx-sl)*K+abs(ey-eu)*K);
ans=min(ans,dis(sl,sy,ex,ed)+abs(sx-sl)*K+abs(ey-ed)*K);
ans=min(ans,dis(sl,sy,el,ey)+abs(sx-sl)*K+abs(ex-el)*K);
ans=min(ans,dis(sl,sy,er,ey)+abs(sx-sl)*K+abs(ex-er)*K);
//right
ans=min(ans,dis(sr,sy,ex,eu)+abs(sx-sr)*K+abs(ey-eu)*K);
ans=min(ans,dis(sr,sy,ex,ed)+abs(sx-sr)*K+abs(ey-ed)*K);
ans=min(ans,dis(sr,sy,el,ey)+abs(sx-sr)*K+abs(ex-el)*K);
ans=min(ans,dis(sr,sy,er,ey)+abs(sx-sr)*K+abs(ex-er)*K);

我们则可以定义 dis(x1,y1,x2,y2) 表示从 (x1,y1) 到 (x2,y2) 的最短距离。具体来讲，可以分为同行、同列、不同行也不同列的 3 种情况。

int dis(int x1,int y1,int x2,int y2){
    if(x1%B==0&&x2%B==0&&y1/B==y2/B){
        int len1=abs(x1-x2)+min(y1%B+y2%B,B*2-y1%B-y2%B);
        int len2=abs(y1-y2)+abs(x1-x2)*K;
        return min(len1,len2);
    }
    if(y1%B==0&&y2%B==0&&x1/B==x2/B){
        int len1=abs(y1-y2)+min(x1%B+x2%B,B*2-x1%B-x2%B);
        int len2=abs(x1-x2)+abs(y1-y2)*K;
        return min(len1,len2);
    }
    return abs(x2-x1)+abs(y2-y1);
}

注意如上判断中，len1 和 len2 表示 2 种不同路径。于是我们有了代码。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,B,K,sx,sy,ex,ey,ans;
int dis(int x1,int y1,int x2,int y2){
    if(x1%B==0&&x2%B==0&&y1/B==y2/B){
        int len1=abs(x1-x2)+min(y1%B+y2%B,B*2-y1%B-y2%B);
        int len2=abs(y1-y2)+abs(x1-x2)*K;
        return min(len1,len2);
    }
    if(y1%B==0&&y2%B==0&&x1/B==x2/B){
        int len1=abs(y1-y2)+min(x1%B+x2%B,B*2-x1%B-x2%B);
        int len2=abs(x1-x2)+abs(y1-y2)*K;
        return min(len1,len2);
    }
    return abs(x2-x1)+abs(y2-y1);
}
signed main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld%lld%lld%lld",&B,&K,&sx,&sy,&ex,&ey);
        ans=(abs(sx-ex)+abs(sy-ey))*K;
        int su=sy/B*B,eu=ey/B*B;//up
        int sd=su+B,ed=eu+B;//down
        int sl=sx/B*B,el=ex/B*B;//left
        int sr=sl+B,er=el+B;//right
        //up
        ans=min(ans,dis(sx,su,ex,eu)+abs(sy-su)*K+abs(ey-eu)*K);
        ans=min(ans,dis(sx,su,ex,ed)+abs(sy-su)*K+abs(ey-ed)*K);
        ans=min(ans,dis(sx,su,el,ey)+abs(sy-su)*K+abs(ex-el)*K);
        ans=min(ans,dis(sx,su,er,ey)+abs(sy-su)*K+abs(ex-er)*K);
        //down
        ans=min(ans,dis(sx,sd,ex,eu)+abs(sy-sd)*K+abs(ey-eu)*K);
        ans=min(ans,dis(sx,sd,ex,ed)+abs(sy-sd)*K+abs(ey-ed)*K);
        ans=min(ans,dis(sx,sd,el,ey)+abs(sy-sd)*K+abs(ex-el)*K);
        ans=min(ans,dis(sx,sd,er,ey)+abs(sy-sd)*K+abs(ex-er)*K);
        //left
        ans=min(ans,dis(sl,sy,ex,eu)+abs(sx-sl)*K+abs(ey-eu)*K);
        ans=min(ans,dis(sl,sy,ex,ed)+abs(sx-sl)*K+abs(ey-ed)*K);
        ans=min(ans,dis(sl,sy,el,ey)+abs(sx-sl)*K+abs(ex-el)*K);
        ans=min(ans,dis(sl,sy,er,ey)+abs(sx-sl)*K+abs(ex-er)*K);
        //right
        ans=min(ans,dis(sr,sy,ex,eu)+abs(sx-sr)*K+abs(ey-eu)*K);
        ans=min(ans,dis(sr,sy,ex,ed)+abs(sx-sr)*K+abs(ey-ed)*K);
        ans=min(ans,dis(sr,sy,el,ey)+abs(sx-sr)*K+abs(ex-el)*K);
        ans=min(ans,dis(sr,sy,er,ey)+abs(sx-sr)*K+abs(ex-er)*K);
        printf("%lld\n",ans);
    }
    return 0;
}

撒花！