AT_abc224_d.[ABC224D] 8 Puzzle on Graph

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥君在路边捡到了一个拼图。
这个拼图由 $9$ 个顶点和 $M$ 条边组成的无向图，以及 $8$ 个棋子构成。

图中的 $9$ 个顶点分别称为顶点 $1$ 、顶点 $2$ 、 $\ldots$ 、顶点 $9$ ，对于 $i=1,2,\ldots,M$ ，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$ 。
$8$ 个棋子分别称为棋子 $1$ 、棋子 $2$ 、 $\ldots$ 、棋子 $8$ ，对于 $j=1,2,\ldots,8$ ，棋子 $j$ 放在顶点 $p_j$ 上。这里保证所有棋子都放在不同的顶点上。请注意，有且仅有一个没有棋子的“空顶点”。

高桥君可以对这个拼图进行如下操作，次数不限（可以为 $0$ 次）：

选择一个与空顶点相邻的顶点上的棋子，将该棋子移动到空顶点上。

高桥君希望通过重复上述操作，使拼图“完成”。当满足以下状态时，拼图被认为是完成的：

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

请判断高桥君是否能够完成拼图。如果可以，请输出完成所需操作次数的最小值；如果无法完成，请输出 $-1$ 。

输入格式

输入以如下格式从标准输入读入：

$M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
$p_1$ $p_2$ $\ldots$ $p_8$

输出格式

如果高桥君能够完成拼图，输出完成所需操作次数的最小值。
如果无法完成，输出 $-1$ 。

输入输出样例

输入#1
```
5
1 2
1 3
1 9
2 9
3 9
3 9 2 4 5 6 7 8
```
输出#1
```
5
```
输入#2
```
5
1 2
1 3
1 9
2 9
3 9
1 2 3 4 5 6 7 8
```
输出#2
```
0
```

输入#3

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

输出#3

-1

输入#4

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

输出#4

说明/提示

限制条件

$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'}$
所有输入均为整数

样例解释 1

通过如下步骤，可以在 $5$ 次操作内完成拼图：

将棋子 $2$ 从顶点 $9$ 移动到顶点 $1$ 。
将棋子 $3$ 从顶点 $2$ 移动到顶点 $9$ 。
将棋子 $2$ 从顶点 $1$ 移动到顶点 $2$ 。
将棋子 $1$ 从顶点 $3$ 移动到顶点 $1$ 。
将棋子 $3$ 从顶点 $9$ 移动到顶点 $3$ 。
无法在少于 $5$ 次操作内完成拼图，因此输出 $5$ 。
请注意，给定的图不一定是连通的。

样例解释 2

拼图一开始就已经完成，因此完成所需的最小操作次数为 $0$ 。

样例解释 3

无法通过操作完成拼图，因此输出 $-1$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页