题解 P1686 【挑战】

· · 题解

第二道大模拟，祭之

不过这道题感觉不像大模拟的亚子？

首先注意到一句话：

捷径必须是直线。

所以起点终点要么横坐标相同要么纵坐标相同。

那就好办了鸭！

横纵坐标分别求一次就可以了，找到每一对 横、纵坐标有一个相同 的点找到之中的最短距离即可。

注意不能出现本来就能从起点走向终点的“捷径”。

代码解析

为了方便排序，先为每一个点创立一个结构体：

struct path{
    int x,y,st;
}p[250005];

x , y 分别是横纵坐标，st 是这个点的编号。

然后，根据输入的 NESW 来初始化每一个点。

    p[0].x=p[0].y=p[0].st=0;//设起始点为（0,0）
    for(int i=1;i<=n;i++){
        ch=getchar();
        while(ch<'A'||ch>'Z') ch=getchar();//防止读取到换行、空格
        switch(ch){
            case 'N':p[i].x=p[i-1].x+1;p[i].y=p[i-1].y;break;
            case 'S':p[i].x=p[i-1].x-1;p[i].y=p[i-1].y;break;
            case 'W':p[i].y=p[i-1].y-1;p[i].x=p[i-1].x;break;
            case 'E':p[i].y=p[i-1].y+1;p[i].x=p[i-1].x;break;
        }
        p[i].st=i;
    }

先根据横坐标排一次序。

bool cmp1(path a,path b){
    return a.x<b.x||a.x==b.x&&a.y<b.y;
}
    sort(p+1,p+n+1,cmp1);

注意此处不能仅根据横坐标排序，在横坐标相同时应按照纵坐标排序。

这样处理后，在算最短距离时就可以只算纵坐标相邻的两个点的距离，大大节省时间。

然后是重点部分，用注释的方式讲解。

    for(int i=2;i<=n;i++){
        if(p[i].x!=p[i-1].x||abs(p[i].st-p[i-1].st)==1) continue;
        // 如果与前一个点横坐标不同则不能形成捷径。
        // 如果两个点编号是相邻的则不能算作“捷径”。
        int d=abs(p[i].y-p[i-1].y),ssp,eep;
        // d是两点的距离,ssp是两点中的起点，eep是两点中的终点
        char ddir;//捷径的方向
        if(p[i].st<p[i-1].st){//如果纵坐标大的反而编号小
            ssp=p[i].st;eep=p[i-1].st;//起点是编号小的那一个
            ddir='W';//方向是向西（需要自己推一下哦）
        }
        else{//同理
            ssp=p[i-1].st;eep=p[i].st;
            ddir='E';
        }
        bool chag=false;//是否更新答案
        if(d<mind) chag=true;
        //mind存储最短距离
        //如果当前距离小于最短距离则更新
        else if(d==mind){//如果当前距离等于最短距离
            if(ssp<sp) chag=true;//选择起始点编号小的那一个
            else if(ssp==sp){//如果起始点相同
                if(eep>ep) chag=true;//选择终点编号大的那一个
            }
        }
        if(chag){//如果需要更新
            sp=ssp;ep=eep;dire=ddir;mind=d;
        }

纵坐标的处理也同理，代码几乎一致，不再赘述。

如果有疑问见下面代码。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct path{
    int x,y,st;
}p[250005];
bool cmp1(path a,path b){
    return a.x<b.x||a.x==b.x&&a.y<b.y;
}
bool cmp2(path a,path b){
    return a.y<b.y||a.y==b.y&&a.x<b.x;
}
int n,mind,sp,ep;
char ch,dire;
int main(){
    scanf("%d",&n);
    p[0].x=p[0].y=p[0].st=0;
    for(int i=1;i<=n;i++){
        ch=getchar();
        while(ch<'A'||ch>'Z') ch=getchar();
        switch(ch){
            case 'N':p[i].x=p[i-1].x+1;p[i].y=p[i-1].y;break;
            case 'S':p[i].x=p[i-1].x-1;p[i].y=p[i-1].y;break;
            case 'W':p[i].y=p[i-1].y-1;p[i].x=p[i-1].x;break;
            case 'E':p[i].y=p[i-1].y+1;p[i].x=p[i-1].x;break;
        }
        p[i].st=i;
    }
    mind=250001;
    sort(p+1,p+n+1,cmp1);
    for(int i=2;i<=n;i++){
        if(p[i].x!=p[i-1].x||abs(p[i].st-p[i-1].st)==1) continue;
        int d=abs(p[i].y-p[i-1].y),ssp,eep;
        char ddir;
        if(p[i].st<p[i-1].st){
            ssp=p[i].st;eep=p[i-1].st;
            ddir='W';
        }
        else{
            ssp=p[i-1].st;eep=p[i].st;
            ddir='E';
        }
        bool chag=false;
        if(d<mind) chag=true;
        else if(d==mind){
            if(ssp<sp) chag=true;
            else if(ssp==sp){
                if(eep>ep) chag=true;
            }
        }
        if(chag){
            sp=ssp;ep=eep;dire=ddir;mind=d;
        }
    }
    sort(p+1,p+n+1,cmp2);
    for(int i=2;i<=n;i++){
        if(p[i].y!=p[i-1].y||abs(p[i].st-p[i-1].st)==1) continue;
        int d=abs(p[i].x-p[i-1].x),ssp,eep;
        char ddir; 
        if(p[i].st<p[i-1].st){
            ssp=p[i].st;eep=p[i-1].st;
            ddir='S';
        }
        else{
            ssp=p[i-1].st;eep=p[i].st;
            ddir='N';
        }
        bool chag=false;
        if(d<mind) chag=true;
        else if(d==mind){
            if(ssp<sp) chag=true;
            else if(ssp==sp){
                if(eep>ep) chag=true;
            }
        }
        if(chag){
            sp=ssp;ep=eep;dire=ddir;mind=d;
        }
    }
    cout<<mind<<" "<<sp<<" "<<ep<<" "<<dire;
    return 0;
}