No.1028 闇討ち

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 118
作問者 : ThistleThistle / テスター : RhoRho
8 ProblemId : 4146 / 出題時の順位表
問題文最終更新日: 2020-04-17 21:40:56

問題文

あなたはPAKEN社を知っているだろうか?この会社の業務は、「PAっぱらぱーなKEN究」をすることである。ここでは略してPAKEN社とする。
PAKEN社ではドローンを自動で飛ばす研究をしており、この度長年の悲願である自動操縦ドローンの開発に成功した。

次に、あなたはKCLC社を知っているだろうか?この会社の業務は「開成で複雑な言語を作る(Kaisei Complex Language Create)」ことである。KCLC社も一足先にドローンの開発に成功しており、発売開始まであと少しである。
KCLC社の研究の進捗に危機感を持ったPAKEN社長全列挙は、開発したドローンでKCLC社員を攻撃し、破壊工作を行うようあなたに指示を出した。

KCLC社員は合計で$N$人おり、各社員には$1$ ~ $N$の番号がつけられている。
KCLC社員はKaisei Cityに住んでおり、Kaisei Cityは $N$ 行 $N$ 列のマス目に区切られている。このマス目の上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ とする。
また、Kaisei Cityの各マス目 $(i,j)$ には社員$A_{i,j}$の家が建っている。
各社員はそれぞれN個ずつの家を持っており、各マス目$(i,j)$の家を所有している人は社員$A_{i,j}$ただ一人である。
つまり、$A_{i,j}=k\ (1\leq k\leq N)$となる$(i,j)$はちょうど$N$個ある。

この情報を受けて、あなたは以下のような襲撃計画を立てた。襲撃計画を始める前に、あなたは$(1,1)$にいる。

  1. 以下の行動を好きな回数だけ行う。
    • $1$ 以上 $N$ 以下の整数$i$ を選ぶ。
    • KCLC社員 $i$ が持っている$N$個の家それぞれに向かって $1$ 台ずつドローンを飛ばす。
  2. 現在のマス目を$(x,1)$として、$(x+1,1)$へ移動する。ただし、現在の位置が$(N,1)$ならば計画を終了する。
この行動で、選ばれない社員があってはいけない。また、同じ社員を二度以上選ぶことも許されない。

発射されたドローンの移動法は以下である。
ドローンが今座標$(x,y)$にいるとする。
・この家が目標の家である場合、移動を停止し、攻撃を行う。
・そうでない場合、$(x+i, y+j) \left(-1 \leq i \leq 1 , -1 \leq j \leq 1 , (i,j) ≠ (0,0) \right)$の8個の座標のうちのどれかに移動する。この移動を$1$回とする。

また、ドローンは目標の家への移動回数が最小になるように移動する。

さて、KCLC社員は奇妙な言語を発することによってドローンを撃墜することができる。
ドローンを撃墜されたくないあなたは、ドローンをある社員の家に向かって発射する場所を、その社員の$N$個の家に向かうドローン全ての移動回数の総和が最小になる地点にすることにした。

ドローンのバッテリーを調整する必要があるので、あなたは事前に$N\times N$台全てのドローンの移動回数の合計を求める事にした。

入力

$N$
$A_{1,1}\ A_{1,2}\ \dots\ A_{1,N}$
$\dots$
$\dots$
$\dots$
$A_{N,1}\ A_{N,2}\ \dots\ A_{N,N}$

入力は全て整数である
$1 \leq N \leq 1000$
$1 \leq A_{i,j} \leq N (1 \leq i,j \leq N)$
それぞれの$A_{i,j}$はちょうど$N$個ずつある

出力

ドローンの移動回数の合計の最小値を1行に出力してください。

サンプル

サンプル1
入力
4
2 4 3 1
1 3 2 4
4 2 1 3
1 4 3 2
出力
28

社員1の家に攻撃を仕掛けるとき、ドローンは地点$(4,1)$から出発させるのが最適で、移動回数の総和は$7$です。
社員2の家に攻撃を仕掛けるとき、ドローンは地点$(2,1)$から出発させるのが最適で、移動回数の総和は$7$です。
社員3の家に攻撃を仕掛けるとき、ドローンは地点$(2,1)$から出発させるのが最適で、移動回数の総和は$8$です。
社員4の家に攻撃を仕掛けるとき、ドローンは地点$(3,1)$から出発させるのが最適で、移動回数の総和は$6$です。
これらの総和である、$7+7+8+6=28$が答えとなります。

サンプル2
入力
5
2 2 3 1 1
4 2 2 3 5
1 4 5 4 1
5 1 3 4 5
3 4 3 5 2
出力
54

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。