Score : $500$ points

问题描述

在一个无限二维网格中，有一个清洁机器人位于点 $(0, 0)$ 处。

该机器人将获得一个由四种字符 L、R、U、D 组成的字符串表示的程序。
它会从左到右读取程序中的字符，并对每个读取的字符执行以下操作。

1. 设 $(x, y)$ 是机器人当前所在的方格坐标。
2. 根据读取到的字符做出如下移动：
   • 如果读取到 L：移动到 $(x-1, y)$。
   • 如果读取到 R：移动到 $(x+1, y)$。
   • 如果读取到 U：移动到 $(x, y-1)$。
   • 如果读取到 D：移动到 $(x, y+1)$。

给定一个由 L、R、U、D 组成的字符串 $S$，机器人将执行的程序是将 $S$ 连接 $K$ 次后的结果。

机器人至少访问过一次的所有方格（包括初始位置 $(0, 0)$）都将被清理。
请输出在程序执行结束后将被清理的方格数量。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a cleaning robot on the square $(0, 0)$ in an infinite two-dimensional grid.

The robot will be given a program represented as a string consisting of four kind of characters L, R, U, D.
It will read the characters in the program from left to right and perform the following action for each character read.

1. Let $(x, y)$ be the square where the robot is currently on.
2. Make the following move according to the character read:
   • if L is read: go to $(x-1, y)$.
   • if R is read: go to $(x+1, y)$.
   • if U is read: go to $(x, y-1)$.
   • if D is read: go to $(x, y+1)$.

You are given a string $S$ consisting of L, R, U, D. The program that will be executed by the robot is the concatenation of $K$ copies of $S$.

Squares visited by the robot at least once, including the initial position $(0, 0)$, will be cleaned.
Print the number of squares that will be cleaned at the end of the execution of the program.

Constraints

• $S$ is a string of length between $1$ and $2 \times 10^5$ (inclusive) consisting of L, R, U, D.
• $1 \leq K \leq 10^{12}$

Input

Input is given from Standard Input in the following format:

$S$

$K$

Output

Print the number of squares that will be cleaned at the end of the execution of the program.

Sample Input 1

RDRUL
2

Sample Output 1

7

The robot will execute the program RDRULRDRUL. It will start on $(0, 0)$ and travel as follows:
$(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) \rightarrow (2, 1) \rightarrow (2, 0) \rightarrow (1, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 0) \rightarrow (2, 0)$.
In the end, seven squares will get cleaned: $(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)$.

Sample Input 2

LR
1000000000000

Sample Output 2

2

Sample Input 3

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

Sample Output 3

219911485785

update @ 2024/3/10 09:42:16