SRM489 Div2 1000

問題

チェスボードと、複数のナイトかポーンがある。
初期配置と最終配置が与えられる。
1手で1つのコマを1回動かせる。各コマの動きは以下。
・ナイトは、ボードからはみ出ないように全方向の桂馬飛びで移動できる
・ポーンは、1マス進める。一番端まで移動すると、ナイトに変化し、その後はナイトとして動く

さらに、各マスには複数のコマが存在してよい。
初期配置から最終配置まで最小で何手かかるか。

考え方

単純なBFSでは、状態数が多くなりすぎてしまうのでダメ。

各マスに複数のコマが存在してよいことから、各コマを動かすときは他のコマを無視して、それだけ独立に動かせる。
初期配置のコマiが最終配置のコマjになるときの手数は、単純にBFSで求められる。
すべての初期配置のコマから最終配置のコマへの手数をadj[i][j]とすると、
2部グラフでのコストが最小になるようにマッチングを取ればよい。
PからNになるものについては、いったん端まで移動してNになってから手数を数えればよい。
ここで、負の値(-1倍)で扱うことで最大となるようなマッチングにできるので、それを求めればよい。

最大流がたぶんよいけど、ハンガリアン法O(n^3)でできる。