狼与故事的开始

Description

不知从多久前的这个村庄,在风中摇曳的饱满麦穗,就被比作狼在奔跑。被风吹倒的麦穗,是被狼踩踏,青黄不接时则是为狼所食。起初的我一无所有,有的只是一点点温暖。于是,我缔结了一个约定,保佑这个村子风调雨顺。

邂逅与离别反复交替,人类终究做到了只凭自己的力量取得丰收,或许我不必再信守约定了。

但是,时间已过去数百年,我该去哪里呢?

这个村庄总有许许多多的旅行商人来来往往,或许他们的马车可以把我带到意想不到的地方。我决定,跳上第一个路过我身边的且看上去不错的人的车,如果有多个商人同时到达,我就跳上好感度最高的人的车,每个人的好感度都不同。

故事正式开始,主人公名叫Holo。

一共有NN个旅行商人,每个旅行商人都有一个起始点(X_i,Y_i)(Xi​,Yi​),旅行商人每分钟可以向上,下,左,右四个方向之一移动一个单位,每个旅行商人的路线在输入数据中给出。

凡是好感度不低于KK的人,Holo都觉得看上去不错。

因为现在是丰收的季节,Holo只能躲在麦堆里,因此,她的位置(Pa,Pb)(Pa,Pb)不会变化。

Input

首先输入TT,表示数据组数。

接下来每组数据中:

第一行输入三个整数Pa,Pb,KPa,Pb,K,前两个表示Holo的位置,最后一个表示Holo的好感度下限。

第二行输入NN,表示旅行商人的人数。

接下来重复NN次,首先输入旅行商人的起始位置(X_i,Y_i)(Xi​,Yi​)与Holo对他的好感度k_iki​,换行后输入商人的旅行路线。用一个只含U,D,L,RU,D,L,R四种字符的字符串表示,假设商人当前位置为(tx,ty)(tx,ty),UU表示向上走(tx+1,ty)(tx+1,ty),DD表示向下走(tx-1,ty)(tx−1,ty),LL表示向左走(tx,ty-1)(tx,ty−1),RR表示向右走(tx,ty+1)(tx,ty+1)。

T\le10T≤10

N\le10N≤10

-1000,000,000\le Pa,Pb,X_i,Y_i \le 1000,000,000−1000,000,000≤Pa,Pb,Xi​,Yi​≤1000,000,000

0\le K,k_i \le10000≤K,ki​≤1000

表示商人路线的字符串长度小于100,000100,000,只包含U,D,L,RU,D,L,R

Output

对于每一组数据,输出一个整数DD,表示Holo会跳上第DD个旅行商人的车(从11开始计数)。如果没有一个旅行商人经过,输出-1−1。

Sample Input 1 

2
2 4 100
2
3 1 113
URLRRRUDLRDDULDLUDDUL
0 0 230
UURRRR
-1 3 80
3
0 1 80
DRRLRLDLRU
-1 3 60
UUUDLLUDDDRRRRRRULLDULUD
1 2 90
LRLRDDULRDRRUDLURD

Sample Output 1

2 

1

题解:模拟每个商人的路径,用结构体存一下

//
//  main.cpp
//
//
//  Created by Edwin on 2018-12-23.
//  Copyright © 2018 Edwin. All rights reserved.
//
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0×7ffffff
#define EPS 1e-8
#define maxn 1000000+10
#define PI acos(-1.0)
#define pb push_back
using namespace std;
struct nobe
{
    int t,kx;
    int num;
}p[maxn];

int cmp(nobe a,nobe b)
{
    if(a.t<b.t) return 1;
    if(a.t==b.t&&a.kx>b.kx) return 1;
    return 0;
}
int main()
{
    int test,n,m;
    cin>>test;
    getchar();
    while(test--)
    {
        int px,py,k;
        cin>>px>>py>>k;
        getchar();
        int n;
        cin>>n;
        getchar();
        int flag=1;
        for(int i=1;i<=n;i++)
        {
            p[i].num=i;
            int x,y;
            cin>>x>>y>>p[i].kx;
            getchar();
            string a;
            getline(cin,a);
            if(p[i].kx<k) {p[i].t=2147483644;continue;}
            if(x==px&&y==py)
            {
                p[i].t=0;flag=0;continue;
            }
            for(int j=1;j<=a.length();j++)
            {
                //cout<<x<<" "<<y<<endl;
                if(a[j-1]=='U') x++;
                if(a[j-1]=='D') x--;
                if(a[j-1]=='L') y--;
                if(a[j-1]=='R') y++;
                if(x==px&&y==py)
                {
                    p[i].t=j;flag=0;break;
                }
            }
        }
        sort(p+1,p+1+n,cmp);
        if(flag) cout<<"-1"<<endl;
        else cout<<p[1].num<<endl;
    }
    return 0;
}

 

发表评论,支持MarkDown语法