AtCoder Beginner Contest 224 D 問題 8 Puzzle on Graph

問題

提出解答

問題の概要

$9$ 頂点 ( $1,2, \cdots, 9$ ) $M$ 辺からなる無向単純グラフ $G=(\{1,2,\dots, 9\}, E=\{u_j v_j \mid j=1,2, \dots, M \})$ と $8$ 個のコマが与えられ, コマ $i$ は頂点 $p_i$ に置かれており, ある頂点に $2$ 個以上のコマが置かれていることはない. ※ちょうど $1$ 頂点にはコマがない.

コマを辺に沿ってコマがない頂点に移動させるとき, 以下のような状況にすることは可能か? また, 可能ならば, それは最短何手か?

$i=1,2, \dots, 8$ に対して, コマ $i$ は頂点 $i$ にある.

制約

$0 \leq M \leq 36$
$1 \leq u_i, v_j \leq 9$
$G$ は単純グラフ
$1 \leq p_i \leq 9$
$i \neq j \Rightarrow p_i \neq p_j$

解法

コマが置かれている状況を列で表す. 長さ $9$ の列 $a=(a_1, \dots, a_8, a_9)$ と, 以下を対応させる.

頂点 $1$ にはコマ $a_1$ があり, $\cdots$ , 頂点 $9$ にはコマ $a_9$ がある (ただし, 頂点 $i$ にコマが無い場合は $a_i=0$ とする).

ここで, $a$ は $(1,2, \cdots, 8,0)$ の並び替えであり, 逆に $(1,2, \dots, 8,0)$ の並び替えに対応するようなコマの状況が存在する. よって, $(1,2, \dots, 8,0)$ の並び替えと同一視し, 並び替え全体の集合を $\mathcal{A}$ とすると, $|\mathcal{A}|=9!=362880 \leq 4 \times 10^5$ である.

この同一視により, $a \in \mathcal{A}$ の状況で, 辺 $uv \in E$ によって, 頂点 $u$ にあるコマをコマが無い頂点 $v$ に移動させることは以下で表すことができる.

$a_v=0$ であるような $uv \in E$ に対して, $a$ の $a_u$ と $a_v$ を入れ替える.

$a \in \mathcal{A}, 1 \leq u,v \leq 9$ において, $\Phi(a,u,v)$ で $a$ において, $a_u,a_v$ を交換した順列とすることにする. $\mathcal{E}$ を

$\mathcal{E}=\{a \Phi(a,u,v) \mid a \in \mathcal{A}, uv \in E \}$

としたときのグラフ $\mathcal{G}=(\mathcal{A}, \mathcal{E})$ は以下のようになる (一部再掲).

$\mathcal{A}$ はコマの状況全てを表す集合 (1対1対応)
$a,b \in \mathcal{A}$ に対して, $ab \in \mathcal{E}$ ならば, $a$ から1手で $b$ にすることができ, 逆も成立する.

このことから, 初期状態に対応する $\mathcal{A}$ の元を $\alpha$ , 目指すべき状態に対応する $\mathcal{A}$ の元を $\beta$ とすると, 求めるべき答えは $\mathcal{G}$ 上に $\alpha \beta$ パスが存在するか? 存在するならばその最短距離を求めることに対応する.