← 返回题目列表

Codeforces · 132/B

B. 皮特

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

Piet 是最著名的视觉深奥编程语言之一。 Piet 中的程序是由彩色像素块构建的,并使用相当复杂的规则进行解释。在这个问题中,我们将使用具有简化规则的 Piet 语言子集。

该程序将是由彩色和黑色像素组成的矩形图像。每个像素的颜色将由 0 到 9 之间的整数给出(含 0 和 9),其中 0 表示黑色。像素块定义为相同颜色(非黑色)像素的矩形。保证所有连接的相同颜色的彩色像素组将形成矩形块。黑色像素组可以形成任意形状。

该程序是通过指令指针(IP)的移动来解释的,它由三部分组成:

- 当前块指针(BP);请注意,块内没有当前像素的概念;
- 方向指针(DP),可以指向左、右、上、下;
- 块选择器(CP),可以从 DP 给定的方向指向左侧或右侧;以绝对值表示,CP 与 DP 可以分别逆时针或顺时针相差 90 度。

最初BP指向包含程序左上角的块,DP指向右侧,CP指向左侧(见下图中的橙色方块)。

程序解释的一步通过以下方式改变IP的状态。解释器找到当前颜色块在 DP 方向上最远的边缘。从形成该边缘的所有像素中,解释器选择 CP 方向最远的像素。此后,BP尝试从该像素沿DP方向移动到下一个像素。如果下一个像素属于彩色块,则该块将成为当前块,并且 IP 的其他两个部分保持不变。如果下一个像素为黑色或在程序之外,BP 保持不变,但 IP 的其他两个部分发生变化。如果 CP 原来指向左侧,现在它指向右侧,并且 DP 保持不变。如果 CP 原本指向右侧,现在它指向左侧,并且 DP 顺时针旋转 90 度。

这样BP就永远不会指向黑色块(保证程序的左上角像素不会是黑色)。

为您提供了一个 Piet 程序。你必须找出程序的哪个块在n步之后将是当前的。

输入

输入的第一行包含两个整数 m (1 ≤ m ≤ 50) 和 n (1 ≤ n ≤ 5·107)。接下来的 m 行包含程序的行。所有线条的长度相同,介于 1 到 50 像素之间,并由字符 0 到 9 组成。第一行的第一个字符不会等于 0。

输出

输出经过n步程序解释后当前块的颜色。

示例

输入 #1

2 10
12
43

输出 #1

1

输入 #2

3 12
1423
6624
6625

输出 #2

6

输入 #3

5 9
10345
23456
34567
45678
56789

输出 #3

5

注意

在第一个示例中,IP 按以下方式更改。第 1 步之后,块 2 成为当前块,并在另外两个步骤后保持不变。在第 4 步之后 BP 移动到块 3,在步骤 7 之后移动到块 4,最后在第 10 步之后 BP 返回到块 1。

IP的状态顺序如图所示:箭头顺时针穿过,主箭头表示DP方向,一侧表示CP方向。