被隔离的街道的大门

Translation by KSkun

原题：問題「隔離された街のゲート」 | エンジニアが死滅シタ世界 〜アンドロイドとふたりぼっちで生きろ〜

问题描述

你找到了一个未完成的游戏程序，这个游戏没有实现控制角色移动的方法。

这个未完成的游戏使用宽为 W 高为 H 的网格图作为地图。
左下角的点是原点，坐标是 (0, 0) 。
从原点横向前进 x 单位，纵向前进 y 单位到达的点坐标表示为 (x, y) 。

现在由于处于开发阶段，地图上没有障碍物，角色的初始坐标为 (0, 0) 。
从该状态开始，执行总共 N 个的向上、下、左或右的移动操作。
各个移动操作对角色坐标 (x, y) 的更改情况如下所示：

• 向上移动：将角色的坐标从 (x, y) 变为 (x, y + 1) 。
• 向下移动：将角色的坐标从 (x, y) 变为 (x, y – 1) 。
• 向左移动：将角色的坐标从 (x, y) 变为 (x – 1, y) 。
• 向右移动：将角色的坐标从 (x, y) 变为 (x + 1, y) 。

在开发需求文档中，需要编写一个能够判断角色在 N 次移动操作的过程中是否处于不合法的坐标上。
这里的不合法的坐标指的是在地图之外的坐标，也就是地图上不存在的坐标。
例如，输入输出样例1和2可以表示如下。

输入格式

H W N 
d_1 
... 
d_N

• 第一行包含三个整数，分别是地图的高 H 、宽 W 和移动操作的次数 N ，数值之间用一个半角空格分隔。
• 接下来的 N 行，第 i (1 ≦ i ≦ N) 行包含一个字符，代表第 i 次移动操作的方向。”U“代表向上，”D“代表向下，”L“代表向左，”R“代表向右。
• 输入数据一共包含 N + 1 行，输入的的末尾包含一个空行。

输出格式

在 N 次移动操作中，如果角色到达了不合法的坐标，则输出一行“invalid”，否则输出一行“valid”。

条件

• 1 ≦ H, W ≦ 50
• 1 ≦ N ≦ 500
• 对于任意 i (1 ≦ i ≦ N) ， d_i 的值为大写英文字母”U”、”D”、”L”、”R”中的一个。

输入输出样例

输入输出样例1

输入：

3 3 5 
U 
R 
D 
R 
L

输出：

valid

输入输出样例2

输入：

4 4 7 
U 
U 
R 
R 
R 
R 
D

输出：

invalid

题解

// Code by KSkun, 2019/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    LL res = 0, neg = 1; char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

inline char readsingle() {
    char c;
    while(!isgraph(c = fgc())) {}
    return c;
}

inline bool isop(char c) {
    return c == 'U' || c == 'D' || c == 'R' || c == 'L';
}

inline char readop() {
    char c;
    while(!isop(c = fgc())) {}
    return c;
}

int n, m, N;

int main() {
    n = readint(); m = readint(); N = readint();
    int nx = 0, ny = 0;
    while(N--) {
        char op = readop();
        if(op == 'U') ny++;
        else if(op == 'D') ny--;
        else if(op == 'L') nx--;
        else if(op == 'R') nx++;
        if(nx < 0 || nx >= n || ny < 0 || ny >= m) {
            puts("invalid"); 
            return 0;
        }
    }
    puts("valid");
    return 0;
}