P1686

miao5 · 2021-04-02 12:56:56 · 题解

题面也是十分简洁了。

就是我们必须在一条路上找到一条捷径。

再看一遍题，我们发现捷径必须是直的。这意味着这条捷径两点的横坐标或者是纵坐标中的一个必须是相同的。

那如何找到横纵坐标相同的两个点呢？

hmmmmmm……

排序！

本题就变为了：在一张图中找最短的横坐标或纵坐标相同的两个点的距离。

之后就是模拟了~~~

code:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n; 
string s;
int ans1=1e9;
int ans2=1e9,ans3=-1e9;
char ans4;
struct node{
    int x;
    int y;
    int e;
}m[250005];
bool cmp1(node a,node b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
bool cmp2(node a,node b){return a.y<b.y||(a.y==b.y&&a.x<b.x);}//两个排序函数。 
void find_x(){
    int num,a,b;
    char p;
    for(int i=1;i<=n-1;i++){
        if(m[i].x==m[i+1].x){//找到相同坐标 
            num=abs(m[i].y-m[i+1].y);//记录长度 
            if(m[i].e<m[i+1].e){//判断出发终止点 
                a=m[i].e;
                b=m[i+1].e;     
                if(m[i].y<m[i+1].y) p='N';//记录方向
                else p='S';
            }
            else{
                a=m[i+1].e;
                b=m[i].e;       
                if(m[i+1].y<m[i].y) p='N';
                else p='S';
            }//另一种 
            if(a+1==b) continue;//如果他们俩已经有路径，不要 
            if(ans1==num){//判断储存答案 
                if(ans2>a){
                    ans1=num; 
                    ans2=a; 
                    ans3=b; 
                    ans4=p;
                }
                else if(ans2==a){
                    if(b>ans3){
                        ans1=num; 
                        ans2=a; 
                        ans3=b; 
                        ans4=p;
                    }
                }
            }
            if(ans1>num){
                ans1=num; 
                ans2=a; 
                ans3=b; 
                ans4=p;
            }

        }   
    }
}
void find_y(){//和上面的一样，只不过是从南北方向转换成东西方向 
    int num,a,b;
    char p;
    for(int i=1;i<=n-1;i++){
        if(m[i].y==m[i+1].y){
            num=abs(m[i].x-m[i+1].x);
            if(m[i].e<m[i+1].e){
                a=m[i].e;
                b=m[i+1].e;     
                if(m[i].x<m[i+1].x) p='E';
                else p='W';
            }
            else{
                a=m[i+1].e;
                b=m[i].e;       
                if(m[i+1].x<m[i].x) p='E';
                else p='W';
            }
            if(a+1==b) continue;
            if(ans1==num){
                if(ans2>a){
                    ans1=num; 
                    ans2=a; 
                    ans3=b; 
                    ans4=p;
                }
                else if(ans2==a){
                    if(b>ans3){
                        ans1=num; 
                        ans2=a; 
                        ans3=b; 
                        ans4=p;
                    }
                }
            }
            if(ans1>num){
                ans1=num; 
                ans2=a; 
                ans3=b; 
                ans4=p;
            }
        }   
    }
}
int main(){
    cin>>n;
    cin>>s;
    m[0].x=0x7fffffff;
    m[0].y=0x7fffffff;
    for(int i=0;i<n;i++){
        int k=i+1;
        m[k].e=k;
        m[k].x=m[k-1].x;
        m[k].y=m[k-1].y;
        if(s[i]=='N') m[k].y++;
        if(s[i]=='W') m[k].x--;
        if(s[i]=='E') m[k].x++;
        if(s[i]=='S') m[k].y--;
    }
    sort(m+1,m+1+n,cmp1);
    find_x();
    sort(m+1,m+1+n,cmp2);
    find_y();//排序与查找 
    cout<<ans1<<" "<<ans2<<" "<<ans3<<" "<<ans4;//输出 
    return 0;
}