CF132B Piet

Piet 是最著名的可视化“恶搞”编程语言之一。Piet 程序由彩色像素块构成，并通过相当复杂的规则进行解释。在本题中，我们将使用 Piet 语言的一个子集，并简化其规则。 程序是一个由彩色像素和黑色像素组成的矩形图像。每个像素的颜色由一个 $0$ 到 $9$ 之间的整数表示，其中 $0$ 表示黑色。一个像素块定义为一组同色（非黑色）的矩形像素。保证所有相同颜色的连通像素组都会形成矩形块。黑色像素组可以形成任意形状。 程序的解释通过指令指针（IP）的移动来进行，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 \leq m \leq 50$）和 $n$（$1 \leq n \leq 5 \cdot 10^{7}$）。接下来的 $m$ 行给出程序的每一行。所有行长度相同，长度在 $1$ 到 $50$ 之间，由字符 $0$-$9$ 组成。第一行第一个字符不为 $0$。

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

在第一个样例中，IP 的变化如下：第 1 步后，BP 移动到块 2，并在接下来的两步保持不变。第 4 步后，BP 移动到块 3，第 7 步后移动到块 4，最后第 10 步 BP 回到块 1。  IP 的状态变化如图所示：箭头按顺时针顺序遍历，主箭头表示 DP 的方向，侧箭头表示 CP 的方向。 由 ChatGPT 4.1 翻译