No.1028 Surprise Attack
Problem Statement
Do you know the company PAKEN? The business of this company is to conduct "PAっぱらぱーなKEN究" (PAppara-pa na KENkyu, "airheaded research"). Here we call it PAKEN for short.
PAKEN has been researching how to fly drones automatically, and it has now succeeded in developing an autonomous drone, its long-cherished goal.
Next, do you know the company KCLC? The business of this company is to "create complex languages at Kaisei (Kaisei Complex Language Create)". KCLC has already succeeded in developing a drone ahead of PAKEN, and its release is just around the corner.
Alarmed by the progress of KCLC's research, Zenretsukyo, the president of PAKEN, has ordered you to attack KCLC's employees with the drones PAKEN developed and to carry out sabotage.
KCLC has $N$ employees in total, and the employees are numbered $1$ to $N$.
The KCLC employees live in Kaisei City, which is divided into a grid of $N$ rows and $N$ columns. Let $(i,j)$ denote the cell in the $i$-th row from the top and the $j$-th column from the left.
On each cell $(i,j)$ of Kaisei City stands a house of employee $A_{i,j}$.
Each employee owns N houses, and the house on each cell $(i,j)$ is owned by employee $A_{i,j}$ alone.
That is, for each $A_{i,j}=k\ (1\leq k\leq N)$, there are exactly $N$ cells $(i,j)$ satisfying it.
Given this information, you have made the following attack plan. Before starting the plan, you are at $(1,1)$.
- Perform the following action any number of times.
- Choose an integer $i$ between $1$ and $N$, inclusive.
- Launch $1$ drone toward each of the $N$ houses owned by KCLC employee $i$.
- Let the current cell be $(x,1)$, and move to $(x+1,1)$. However, if the current position is $(N,1)$, end the plan.
A launched drone moves as follows.
Suppose the drone is currently at coordinates $(x,y)$.
- If the house here is the target house, it stops moving and attacks.
- Otherwise, it moves to one of the 8 coordinates $(x+i, y+j) \left(-1 \leq i \leq 1 , -1 \leq j \leq 1 , (i,j) ≠ (0,0) \right)$. This counts as $1$ move.
Each drone moves so that the number of moves to its target house is minimized.
Now, KCLC employees can shoot down drones by uttering a strange language.
Since you do not want your drones to be shot down, you have decided that the place from which you launch drones toward an employee's houses will be a point that minimizes the sum of the numbers of moves of all the drones heading to that employee's $N$ houses.
Since the drones' batteries need to be adjusted, you have decided to compute in advance the total number of moves of all $N\times N$ drones.
Input
$N$
$A_{1,1}\ A_{1,2}\ \dots\ A_{1,N}$
$\dots$
$\dots$
$\dots$
$A_{N,1}\ A_{N,2}\ \dots\ A_{N,N}$
All inputs are integers.
$1 \leq N \leq 1000$
$1 \leq A_{i,j} \leq N (1 \leq i,j \leq N)$
Each value of $A_{i,j}$ appears exactly $N$ times.
Output
Output the minimum value of the total number of moves of the drones on 1 line.
Sample
Sample 1
Input
4 2 4 3 1 1 3 2 4 4 2 1 3 1 4 3 2
Output
28
When attacking the houses of employee 1, it is optimal to launch the drones from point $(4,1)$, and the sum of the numbers of moves is $7$.
When attacking the houses of employee 2, it is optimal to launch the drones from point $(2,1)$, and the sum of the numbers of moves is $7$.
When attacking the houses of employee 3, it is optimal to launch the drones from point $(2,1)$, and the sum of the numbers of moves is $8$.
When attacking the houses of employee 4, it is optimal to launch the drones from point $(3,1)$, and the sum of the numbers of moves is $6$.
The answer is the sum of these, $7+7+8+6=28$.
Sample 2
Input
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
Output
54
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Rho