codeforces Ciel and Robot

本文从WordPress迁移而来, 查看全部WordPress迁移文章

http://codeforces.com/contest/322/problem/C

模拟,简单数学分析

题意: 编写一个机器人移动程序,机器人一开始在(0,0)处,给出一组移动指令,分别为UDLR,表示向上下左右移动一格;机器人会无限循环执行这段指令,即执行完一轮,在最后停留的位置开始再执行一轮。程序给出一个目标位置,问机器人能否到达这个位置,输出Yes,No(其实可以问要多少步才能到达,方法一样,多了一个计算而已,只判断Y/N就简单些)

用偏移量来解决,步骤

  1. 指令条数只有100,第一轮,按照指令走一次,把每步到达的坐标保存下来。在走的过程中,可以顺便判断一下到达的点是不是终点,是的话直接跳出Yes即可
  2. 走完一轮后,得到最后停留的位置,设为(x,y)。那么终点和起点(0,0)在坐标上有一个偏移量(dx,dy),刚好 就是其本身(dx = x - 0 , dy = y - 0)。这个位置是第1轮的终点也是下一轮的起点。可以试着再走一轮,然后和第1轮对比的点对比,很容易知道,对应的点的偏移量都是(dx,dy)。所以我们以第1轮走过的点为标准,可以推出每一轮的对应点的位置(不断累加偏移量即可)
  3. 要判断终点能不能到达,就枚举第1轮走过的每个点,看看这个点通过不断累加偏移量能不能到达终点,这个累加的过程用数学一步就能判断出来
  4. 注意特别的情况,即dx = 0,dy = 0这些情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <string>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>

string str; //指令
vector<pii>point; //第1轮走过的每个位置
int dx,dy; //偏移量
int tx,ty; //终点

int main(){
int index;
bool res;
cin >> tx >> ty;
cin >> str;
point.clear();
point.pb(mp(0,0));
res = false;
index = 0;
for(int i = 0; i < str.length(); i++){
int x,y;
int x0 = point[index].first;
int y0 = point[index].second;
if(str[i] == 'U')
x = x0 , y = y0 + 1;
else if(str[i] == 'D')
x = x0 , y = y0 - 1;
else if(str[i] == 'L')
x = x0 - 1 , y = y0;
else
x = x0 + 1 , y = y0;
if(x == tx && y == ty){
res = true;
break;
}
point.pb(mp(x,y));
index++;
}
if(res){
puts("Yes");
return 0;
}
dx = point[index].first;
dy = point[index].second;
point.pop_back();
if(dx == 0 && dy == 0){
puts("No");
return 0;
}

for(int i = 0; i < point.size(); i++){
int x0 = point[i].first;
int y0 = point[i].second;
if(dx && dy){
if((tx - x0) % dx != 0 || (tx - x0) / dx < 0) continue;
if((ty - y0) % dy != 0 || (ty - y0) / dy < 0) continue;
if((tx - x0) / dx == (ty - y0) / dy){
res = true;
break;
}
}
else if(dx == 0){
if(tx != x0) continue;
if((ty - y0) % dy == 0 && (ty - y0) / dy >= 0){
res = true;
break;
}
}
else{
if(ty != y0) continue;
if((tx - x0) % dx == 0 && (tx - x0) / dx >= 0){
res = true;
break;
}
}
}
if(res) puts("Yes");
else puts("No");
return 0;
}