P酱的冒险旅途

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Submit Status

P酱是个可爱的男孩子，有一天他在野外冒险，不知不觉中走入了一块神奇的地方。他在0时刻进入这个地方，每一时刻他都只能向某一特定的方向移动长度为1的距离，当然他也可以选择不移动。移动需要花费1的时间。

各个时刻他允许移动的方向由一个字符串给出，字符串只包含U、D、L、R四种字符，其中U表示向上（y轴正方向）移动，D表示向下（y轴负方向）移动，L表示向左（x轴负方向）移动，R表示向右（x轴正方向）移动。

字符串的第x个字符代表了第x时刻P酱可以移动的方向，字符串的长度只有t，也就是说，超过t时刻，P酱就要被邪恶的魔王大爷抓走了~

现在P酱在坐标原点，即(0,0)点，而出口在(x,y)点，P酱希望在规定的时间t内尽快走到出口。帮助P酱在最短的时间内离开这里吧~

Input

第一行包含一个正数 T (T≤100)，表示数据组数。

接下来每组数据包含两行，第一行包含三个整数 x,y,t (−105≤x,y≤105,0<t≤105)；第二行包含一个长度为t的字符串，第i个字符表示在i时刻他能移动的方向，字符串只包含U，D，L，R四种字母。

Output

对于每组数据输出一行，表示P酱到达出口的最早时刻。如果他无法在t时刻内到达出口，输出-1。

Sample input and output

2

1 -1 5

LDRDR

-2 1 8

RRUDDLRU

3

-1

Hint

第一组样例：

P酱在0时刻位于原点(0,0)，他只能向左移动，但他选择不走。
P酱在1时刻依然位于原点(0,0)，他只能向下移动，于是他向下移动到了(0,−1)
P酱在2时刻位于(0,−1)，他只能向右移动，于是他移动到了出口(1,−1)，所以在3时刻，P酱离开了这片区域！

题解：受着上题的影响，于是苦逼的我果断暴力了(想都没想);然后结果可想而知，肯定超时了。10的5次方，每次两种选择，也就是2的10万次方，不超时才算有鬼了；

没浪费时间直接按照题意写了下，就A了；

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

#define mem(x,y) memset(x,y,sizeof(x))

#define SI(x) scanf("%d",&x)

#define PI(x) printf("%d",x)

#define P_ printf(" ")

const int INF=0x3f3f3f3f;

const int MAXN=1e5+;

char s[MAXN];

int x,y,t;

int main(){

    int T;

    SI(T);

    while(T--){

        scanf("%d%d%d",&x,&y,&t);

        scanf("%s",s+);

        int ans=,nx=,ny=,flot=;

        for(int i=;s[i];i++,ans++){

            if(x==nx&&y==ny){

                flot=;break;

            }

            if(s[i]=='L'){

                if(x<=&&nx>x)nx--;

            }

            if(s[i]=='R'){

                if(x>=&&nx<x)nx++;

            }

            if(s[i]=='U'){

                if(y>=&&ny<y)ny++;

            }

            if(s[i]=='D'){

                if(y<=&&ny>y)ny--;

            }

        }

        if(flot)printf("%d\n",ans);

        else puts("-1");

    }

    return ;

}

暴力超时了，也贴下吧：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

#define mem(x,y) memset(x,y,sizeof(x))

#define SI(x) scanf("%d",&x)

#define PI(x) printf("%d",x)

#define P_ printf(" ")

const int INF=0x3f3f3f3f;

const int MAXN=1e5+;

char s[MAXN];

int x,y,t;

int ans;

void dfs(int nx,int ny,int cur){

    if(cur>t)return;

    if(nx==x&&ny==y){

        ans=min(ans,cur-);

        return;

    }

    dfs(nx,ny,cur+);

    if(s[cur]=='L')dfs(nx-,ny,cur+);

    if(s[cur]=='R')dfs(nx+,ny,cur+);

    if(s[cur]=='U')dfs(nx,ny+,cur+);

    if(s[cur]=='D')dfs(nx,ny-,cur+);

}

int main(){

    int T;

    SI(T);

    while(T--){

        scanf("%d%d%d",&x,&y,&t);

        scanf("%s",s+);

        ans=INF;

        dfs(,,);

        if(ans==INF)puts("-1");

        else printf("%d\n",ans);

    }

    return ;

}

P酱