Atcoder水色精進記録
ABC224
D - 8 Puzzle on Graph
https://atcoder.jp/contests/abc224/tasks/abc224_d
アルゴリズム・データ構造
BFS
考察
操作回数の最小化なのでBFSができないか？
考えられる状態数としては、9個の並び替えなので9!=362,880
全状態探索が可能
1-8空きマス(0)の並びをtupleで管理して状態として、訪れたことがある状態をsetで管理。
再度同じ状態に訪れることがないようにqueに足していく。
現在の状態から1手で訪れることが出来る状態は、freeのマスに繋がっている辺の先の値とfreeをswapすれば求めることが可能
提出
感想
pythonだとsetにlistが入れれないため、tupleにしたが、解説の文字列にするのは思い浮かばなかった。選択肢の候補には出るようにしたい。