全国統一プログラミング王決定戦本戦 C - Come Together
問題概要
H*WのマスからK個の駒を取り除いた環境下で全ての駒を隣接するマスに移動させる操作を繰り返して1つのマス上にもっていくまでの最小手数を求める。
経過
中央値ゲーじゃないか?
(入力例1で実験して)合ってるんじゃない?
実装(配列の初期化が地味に罠。うく。)
できたんじゃないか
あれ?入力例2が合わん。
わお、最終的な目的のマス目の座標を求めるところのループ抜ける条件ミスってるじゃん
(修正)合った。提出。
WA!?*******(ピー)
変な落ち方だしlong longに変えるか
通った。やった。
解法
こういうのは大概中央値を考えるとうまくいって幸せになるのでその方針で考えてみる。
すると、(Rの中央値,Cの中央値)が集めるマスとなることになる。
それを求めたら、あとは各マスからそのマスへのマンハッタン距離を求めて、足す。