← 返回题目列表

Codeforces · 386/D

D. 积分游戏

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

您正在玩以下游戏。平面上有n个点。它们是正 n 多边形的顶点。点用 1 到 n 的整数标记。每对不同的点都由一条对角线连接,该对角线采用 26 种颜色之一着色。点用小写英文字母表示。三块石头位于三个不同的顶点。所有的石头都是一样的。通过一次移动,您可以将石头沿某条对角线移动到另一个自由顶点。这条对角线的颜色必须与连接另外两块石头的对角线的颜色相同。

你的目标是以这样的方式移动石子,使得石子占据的唯一顶点是 1、2 和 3。你必须使用最少的移动次数达到这样的位置。编写一个以最佳方式玩这个游戏的程序。

输入

第一行有一个整数 n (3 ≤ n ≤ 70) — 点数。第二行有三个空格分隔的整数,从 1 到 n - 顶点数,石头最初所在的位置。

以下 n 行中的每一行包含 n 个符号 - 表示对角线颜色的矩阵。颜色用小写英文字母表示。第i行的符号j表示点i和j之间的对角线的颜色。矩阵是对称的,因此第 i 行的第 j 个符号等于第 j 行的第 i 个符号。主对角线充满“*”符号,因为没有对角线,将点连接到其自身。

输出

如果无法在顶点 1、2 和 3 上放置棋子,则在一行上打印 -1。否则,在第一行打印所需的最小移动次数,并在接下来的行中打印每个移动的描述,每行一个移动。要描述一次移动,请打印两个整数。移走石头的起点和移动石头的终点。如果有多个最优解,则打印其中任意一个。

示例

输入 #1

4
2 3 4
*aba
a*ab
ba*b
abb*

输出 #1

1
4 1

输入 #2

4
2 3 4
*abc
a*ab
ba*b
cbb*

输出 #2

-1

注意

在第一个示例中,我们可以将棋子从点 4 移动到点 1,因为这些点由颜色“a”的对角线连接,而对角线连接点 2 和 3(其他棋子所在的位置)由相同颜色的对角线连接。之后,棋子将位于点 1、2 和 3 上。