UESTC--758--P酱的冒险旅途（模拟）

P酱的冒险旅途

Time Limit: 1000MS

Memory Limit: 65535KB

64bit IO Format: %lld & %llu

Submit
Status

Description

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

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

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

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

Input

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

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

Output

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

Sample Input

2

1 -1 5

LDRDR

-2 1 8

RRUDDLRU

Sample Output

3

-1

Hint

第一组样例：

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

超时到死，一直深搜一直wa，简直要崩溃了，原来只是一个规律，，，，，

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

char str[100100];

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		memset(str,'\0',sizeof(str));

		int x,y,t;

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

//		getchar();

		scanf("%s",str);

		long long u,d,l,r;

		u=d=r=l=0;

		if(x>=0) r=x;

		else l=x*-1;

		if(y>=0) u=y;

		else d=y*-1;

		int ans=0;

		for(int i=0;i<t;i++)

		{

			if(u==0&&d==0&&l==0&&r==0)

			{

				ans=i;

				break;

			}

			if(str[i]=='U'&&u>0) u--;

			else if(str[i]=='D'&&d>0) d--;

			else if(str[i]=='L'&&l>0) l--;

			else if(str[i]=='R'&&r>0) r--;

		}

		if(x==0&&y==0)

		printf("0\n");

		else if(ans!=0)

//		printf("%s\n",str);

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

		else printf("-1\n");

	}

	return 0;

}

巴特西

UESTC--758--P酱的冒险旅途（模拟）

最新文章

热门文章