D - 8 Puzzle on Graph

Contest Duration: 2021-10-23(Sat) 12:00 - 2021-10-23(Sat) 13:40 (local time) (100 minutes) Back to Home

D - 8 Puzzle on Graph Editorial

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : $400$ 点

問題文

高橋君は道端であるパズルを拾いました。
このパズルは、 $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$ 回でもよい）だけ行うことができます。

空の頂点に隣接する頂点に置かれたコマを $1$ つ選び、選んだコマを空の頂点に移動する。

高橋君は上記の操作を繰り返して、このパズルを「完成」させようとしています。パズルは、下記の状態を満たしたときに完成となります。

$j = 1, 2, \ldots, 8$ について、コマ $j$ は頂点 $j$ に置かれている。

高橋君がパズルを完成させることが可能かどうかを判定し、可能な場合はそのために必要な操作回数の最小値を出力してください。

制約

$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'}$
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

高橋君がパズルを完成させることが可能な場合は、そのために必要な操作回数の最小値を出力せよ。高橋君がパズルを完成させることが不可能な場合は、 $-1$ を出力せよ。

入力例 1Copy

Copy

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

出力例 1Copy

Copy

下記の手順によって、 $5$ 回の操作でパズルを完成させることができます。

コマ $2$ を頂点 $9$ から頂点 $1$ に移動する。
コマ $3$ を頂点 $2$ から頂点 $9$ に移動する。
コマ $2$ を頂点 $1$ から頂点 $2$ に移動する。
コマ $1$ を頂点 $3$ から頂点 $1$ に移動する。
コマ $3$ を頂点 $9$ から頂点 $3$ に移動する。

一方、 $5$ 回未満の操作でパズルを完成させることはできません。よって、 $5$ を出力します。
与えられるグラフは連結とは限らないことに注意してください。

入力例 2Copy

Copy

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

出力例 2Copy

Copy

パズルは初めから完成しています。よって、完成させるために必要な操作回数の最小値は $0$ 回です。

入力例 3Copy

Copy

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

出力例 3Copy

Copy

-1

操作の繰り返しによってパズルを完成させることができないので、 $-1$ を出力します。

入力例 4Copy

Copy

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

出力例 4Copy

Copy

Score : $400$ points

Problem Statement

Takahashi found a puzzle along some road.
It is composed of an undirected graph with nine vertices and $M$ edges, and eight pieces.

The nine vertices of the graph are called Vertex $1$ , Vertex $2$ , $\ldots$ , Vertex $9$ . For each $i = 1, 2, \ldots, M$ , the $i$ -th edge connects Vertex $u_i$ and Vertex $v_i$ .
The eight pieces are called Piece $1$ , Piece $2$ , $\ldots$ , Piece $8$ . For each $j = 1, 2, \ldots, 8$ , Piece $j$ is on Vertex $p_j$ .
Here, it is guaranteed that all pieces are on distinct vertices. Note that there is exactly one empty vertex without a piece.

Takahashi can do the following operation on the puzzle any number of times (possibly zero).

Choose a piece on a vertex adjacent to the empty vertex, and move it to the empty vertex.

By repeating this operation, he aims to complete the puzzle. The puzzle is considered complete when the following holds.

For each $j = 1, 2, \ldots, 8$ , Piece $j$ is on Vertex $j$ .

Determine whether it is possible for Takahashi to complete the puzzle. If it is possible, find the minimum number of operations needed to do so.

Constraints

$0 \leq M \leq 36$
$1 \leq u_i, v_i \leq 9$
The given graph has no multi-edges or self-loops.
$1 \leq p_j \leq 9$
$j \neq j' \Rightarrow p_j \neq p_{j'}$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

If it is possible for Takahashi to complete the puzzle, find the minimum number of operations needed to do so. Otherwise, print $-1$ .

Sample Input 1Copy

Copy

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

Sample Output 1Copy

Copy

The following procedure completes the puzzle in five operations.

Move Piece $2$ from Vertex $9$ to Vertex $1$ .
Move Piece $3$ from Vertex $2$ to Vertex $9$ .
Move Piece $2$ from Vertex $1$ to Vertex $2$ .
Move Piece $1$ from Vertex $3$ to Vertex $1$ .
Move Piece $3$ from Vertex $9$ to Vertex $3$ .

On the other hand, it is impossible to complete the puzzle in less than five operations. Thus, we should print $5$ .
Note that the given graph may not be connected.

Sample Input 2Copy

Copy

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

Sample Output 2Copy

Copy

The puzzle is already complete from the beginning. Thus, the minimum number of operations needed to complete the puzzle is $0$ .

Sample Input 3Copy

Copy

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

Sample Output 3Copy

Copy

-1

No sequence of operations can complete the puzzle, so we should print $-1$ .

Sample Input 4Copy

Copy

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

Sample Output 4Copy

Copy