ak爷走格子

Description

 

众所周知，ak爷ljx在计科是个人物。。有一天他在玩游戏，就是操作一个机器人上下左右动的游戏。机器人一开始在（0,0）点，经过任意轮的命令之后，问是不是可以走到目标点（当然也不一定非得要走完一整串命令）。ljx很懒，你能帮他看看能否到达目标点吗？命令有四个，分别是‘U’，‘D’，‘L’，‘R’。

U代表往上走：(x, y)  →  (x, y+1);

D代表往下走：(x, y)  →  (x, y-1);

L代表往左走：(x, y)  →  (x-1, y);

R代表往右走：(x, y)  →  (x+1, y)；

Input

 

多组样例输入。直到处理到文件结束（EOF）。一开始是两个整数a,b.代表机器人所到达的目标点（|a|<=1e9,|b|<=1e9）。接下来是一整串的命令（strlen（s）<=100）,里面只有‘U’，‘D’，‘L’，‘R’。

Output

 

如果可以到达目标点，就输出“Yes”，否则就输出“No”。

Sample Input 1 

4 2
UURRDL

Sample Output 1

No

Sample Input 2 

2 6
RUUUURLDDDL

Sample Output 2

Yes

Hint

第一个样例没发到达目标点，嘤嘤嘤。

第二个样例到达了目标点。嘻嘻。

谁能帮ljx做出来，他就请谁吃饭。

 

 

思路：

设走完某一步之后与（0,0）的坐标变化量为（xi,yi）(0<=i<=len-1)(也可以从1开始，无所谓）

设走了k轮之后又走了若干步之后到达（a,b）,一轮的坐标变化量为（x,y）

则a=k*x+xi

    b=k*y+yi

所以a-xi=k*x

        b-yi=k*y

利用其中一个式子求出k，然后带入另一个看看是否满足，满足就能到达

 

错误想法：左右两边取模，得a%x=xi，b%y=yi,然后遍历一遍，看是否有满足的

这样是错的，因为取模的话，这两个k可能是不相同的（嘤嘤嘤）

代码中注释掉的是错误代码

#include<cstdio>
#include<cstring>
using namespace std;
struct node {
	int x,y;
} p[150];
char s[150];
int main() {
	int a,b;
	while(~scanf("%d%d",&a,&b)) {
		scanf("%s",s);
		int len=strlen(s);
		int x=0,y=0;
		bool flag=false;
		if(x==a&&y==b) flag=true;
		if(!flag) {
			for(int i=0; i<len; i++) {
				if(s[i]=='U')
					y++;
				else if(s[i]=='D')
					y--;
				else if(s[i]=='L')
					x--;
				else if(s[i]=='R')
					x++;
				p[i].x=x,p[i].y=y;
			}
//			if(p[len-1].x)
//			a=(a-p[len-1].x)%p[len-1].x;
//			if(p[len-1].y)
//			b=(b-p[len-1].y)%p[len-1].y;
//			for(int i=0;i<len;i++)
//			printf("%3d :%3d %3d\n",i,p[i].x,p[i].y);
//			printf("%d  %d\n",a,b);
//			for(int i=0;i<len-1;i++){
//				if(p[i].x==a&&p[i].y==b){
//					flag=true;
//					break;
//				}
//			}
            int k;
            for(int i=0;i<len;i++){
            	if(x) k=(a-p[i].x)/x;
            	else if(y) k=(b-p[i].y)/y;
            	if(k<0) k=0;
            	if(a==k*x+p[i].x&&b==k*y+p[i].y){
            		flag=true;
            		break;
				}
			}
		}
		if(flag) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}