ABC224 D - 8 Puzzle on Graph (400)
数字がどこにあるかの文字列では無く、その位置に何の数字があるかの文字列で表すことにする
"123456780"になったときの最小移動回数が答え
最初の文字列の移動回数は0
最初の文字列をキューに入れて、キューが空になるまで以下を行う
キューから1つ取り出す
0が入っている位置についてそこから繋がっている点と文字を交換した文字をそれぞれ作り出す
最小距離をその文字列について更新したらキューに入れる
あり得る状態が$ 9!通り、交換して作れる文字列が$ 8通りしかないので制限時間4秒だと間に合う