8 Puzzle on Graph

题目描述

Takahashi 在路上发现了一个拼图。
它由一个有九个顶点和 $M$ 条边的无向图以及八个棋子组成。 图的九个顶点被称为顶点 $1$、顶点 $2$、$\ldots$、顶点 $9$。对于每个 $i = 1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。
八个棋子被称为棋子 $1$、棋子 $2$、$\ldots$、棋子 $8$。 对于每个 $j = 1, 2, \ldots, 8$，棋子 $j$ 在顶点 $p_j$ 上。
这里保证所有棋子位于不同的顶点。 注意恰好有一个空的顶点没有棋子。 Takahashi 可以对拼图执行以下操作任意次（可以为零次）。

选择位于空顶点相邻顶点上的一个棋子，并将其移动到空顶点。

通过重复该操作，他的目标是将拼图“完成”。 当满足以下条件时，拼图被视为完成。

对于每个 $j = 1, 2, \ldots, 8$，棋子 $j$ 在顶点 $j$ 上。

判断 Takahashi 是否可以完成该拼图。如果可以，找出完成此目标所需操作的最小次数。 否则，输出 $-1$。

输入格式

输入从标准输入按以下格式给出： $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$ $p_1$ $p_2$ $\ldots$ $p_8$

输出格式

如果 Takahashi 可以完成拼图，找出完成所需的最小操作次数。 否则，输出 $-1$。

5
1 2
1 3
1 9
2 9
3 9
3 9 2 4 5 6 7 8

5

5
1 2
1 3
1 9
2 9
3 9
1 2 3 4 5 6 7 8

0

12
8 5
9 6
4 5
4 1
2 5
8 9
2 1
3 6
8 7
6 5
7 4
2 3
1 2 3 4 5 6 8 7

-1

12
6 5
5 4
4 1
4 7
8 5
2 1
2 5
6 9
3 6
9 8
8 7
3 2
2 3 4 6 1 9 7 8

16

提示

$0 \leq M \leq 36$ $1 \leq u_i, v_i \leq 9$ 给定的图不存在多重边或自环。 $1 \leq p_j \leq 9$ $j \neq j' \Rightarrow p_j \neq p_{j'}$ 输入中的所有值均为整数。下面的步骤可以在五次操作内完成拼图。

将棋子 $2$ 从顶点 $9$ 移到顶点 $1$。 将棋子 $3$ 从顶点 $2$ 移到顶点 $9$。 将棋子 $2$ 从顶点 $1$ 移到顶点 $2$。 将棋子 $1$ 从顶点 $3$ 移到顶点 $1$。 将棋子 $3$ 从顶点 $9$ 移到顶点 $3$。

另一方面，不可能在少于五次操作内完成拼图。因此，我们应该输出 $5$.
注意给定的图可能不是连通的。
拼图从一开始就已经完成。 因此，完成拼图所需的最小操作次数为 $0$.
没有任何操作序列可以完成拼图，所以我们应该输出 $-1$.

标签: AtCoder|abc224D

来源

AtCoder|abc224D