Badeline

题目

来源：广州大学第十四届ACM大学生程序设计竞赛（同步赛）

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;
}