← 返回题目列表

AtCoder · icpc2015autumn_e

E. 移动矩阵

中文机器翻译题面 查看原题

问题陈述

给定 $N \times N$ 矩阵 $A$,其初始化为 $A_{i,j} = (i-1)N + j$,其中 $A_{i,j}$ 是 $A$ 的第 $i$ 行和第 $j$ 列的条目。请注意,$i$ 和$j$ 是基于$1$ 的。

还为您提供了一个操作序列,其中包含四种类型的移位操作:左移、右移、上移和下移。 更准确地说,这些操作定义如下:

  • $i$ 左移:第 $i$ 行向左循环移位,即将 $2 \leq k \leq N$ 将先前的 $A_{i,k}$ 设置为新的 $A_{i,k-1}$,并将先前的 $A_{i,1}$ 设置为新的 $A_{i,N}$。
  • $i$ 右移:将第 $i$ 行向右循环移位,即将 $1 \leq k \leq N-1$ 将之前的 $A_{i,k}$ 设置为新的 $A_{i,k+1}$,将之前的 $A_{i,N}$ 设置为新的 $A_{i,1}$。
  • $j$ 上移:将第 $j$ 列循环移位到上面,即将 $2 \leq k \leq N$ 将之前的 $A_{k,j}$ 设置为新的 $A_{k-1,j}$,将之前的 $A_{1,j}$ 设置为新的 $A_{N,j}$。
  • $j$ 下移:将第 $j$ 列循环移位到下面,即将 $1 \leq k \leq N-1$ 将之前的 $A_{k,j}$ 设置为新的 $A_{k+1,j}$,将之前的 $A_{N,j}$ 设置为新的 $A_{1,j}$。

操作序列以字符串形式给出。 您必须在给定字符串中从左到右对给定矩阵应用运算。 左移、右移、上移、下移在字符串中分别称为“L”、“R”、“U”、“D”,后面的数字表示要移动的行/列。 例如,“R25”表示我们应该用 25 进行右移。 此外,该概念支持操作序列的重复。 由一对括号包围的操作序列必须精确重复 $m$ 次,其中 $m$ 是右括号后面的数字。 例如,“(L1R2)10”意味着我们应该重复这两个操作的集合正好10次:按顺序左移1,右移2。

给定的操作序列保证遵循以下 BNF:

<sequence> := <sequence><repetition> | <sequence><operation> | <repetition> | <operation>
<repetition> := '('<sequence>')'<number>
<operation> := <shift><number>
<shift> := 'L' | 'R' | 'U' | 'D'
<number> := <nonzero_digit> |<number><digit>
<digit> := '0' | <nonzero_digit>
<nonzero_digit> := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

给定 $N$ 和一个字符串形式的操作序列,编写一个程序来计算操作序列指示的操作后的 $N \times N$ 矩阵。


输入

输入由单个测试用例组成。测试用例的格式如下。

$N$ $L$
$S$

第一行包含两个整数 $N$ 和 $L$,其中 $N$ ($1 \leq N \leq 100$) 是给定矩阵的大小,$L$ ($2 \leq L \leq 1{,}000$) 是以下字符串的长度。 第二行包含一个字符串$S$,表示给定的操作序列。 您可以假设 $S$ 遵循上述 BNF。 您还可以假设表示行和列的数字不少于 $1$ 且不超过 $N$,并且在给定字符串中每次重复的次数不少于 $1$ 且不超过 $10^9$。

输出

输出 $N$ 行运算后的矩阵,其中第 $i$ 行包含单空格分隔的 $N$ 整数,表示运算后 $A$ 的第 $i$ 行。



示例输入 1

3 2
R1

样本输入 1 的输出

3 1 2
4 5 6
7 8 9

示例输入 2

3 7
(U2)300

样本输入 2 的输出

1 2 3
4 5 6
7 8 9

示例输入 3

3 7
(R1D1)3

样本输入 3 的输出

3 4 7
1 5 6
2 8 9