题目
Madeline 和 Badeline 在一个无限大的二维的坐标系内。
一开始 Madeline 在某个位置,然后 Madeline 在接下来的 n 秒钟内向四个方向移动或者不动,这四个方向分别是上下左右四个方向。
如果在这第 1 秒到第 n 秒内 Madeline 与 Badeline 在任何一个时间点都没有在同一个位置就相当于成功通过旧址。
Badeline 在第 t 秒时的位置是 Madeline 在第 t−k 秒时的位置。而第 1 秒到第 k−1 秒内 Badeline 不在任何位置上,即第 1 秒到第 k−1 秒内 Madeline 与 Badeline 不会在同一个位置。在第 k 秒时 Badeline 在 Madeline 第 0 秒时的位置。
移动方向:U 表示向上移动,D 表示向下移动,L 表示向左移动,R 表示向右移动,S 表示不动。
现在给定 Madeline 在第 1 秒到第 n 秒内的移动,判断这样移动的话会不会登山失败。
解题思路
使用 x 和 y 记录 Madeline 从第 0 秒到第 n 秒的位置。当时间大于等于 k 秒时,判断第 i 秒和第 i-k 秒的位置是否相同,若相同,则失败。
C++代码
#include<iostream> #include<vector> using namespace std; string d = "SUDLR"; int di[5][2] = { {0,0}, {0,1}, {0,-1}, {-1,0}, {1,0} }; int main(){ int n, k; cin >> n >> k; string s; cin >> s; vector<int> x(n+1), y(n+1); for(int i=0; i<n; ++i){ for(int j=0; j<5; ++j){ if(s[i]==d[j]){ x[i+1] = x[i] + di[j][0]; y[i+1] = y[i] + di[j][1]; break; } } } bool fail = false; for(int i=k; i<=n; ++i){ if(x[i]==x[i-k] && y[i]==y[i-k]){ fail = true; break; } } if(fail) cout << "no" << endl; else cout << "yes" << endl; return 0; }