問題一覧 > 通常問題

No.1028 Surprise Attack

レベル : / AI推定難易度 : 1325 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 144
作問者 : Thistle / テスター : Rho
お気に入りにしたユーザー ProblemId : 4146 / 自分の提出
問題文最終更新日: 2020-04-17 21:40:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 244 (順位表) の他の問題:

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)$.

  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$.
  2. Let the current cell be $(x,1)$, and move to $(x+1,1)$. However, if the current position is $(N,1)$, end the plan.
Through these actions, no employee may be left unchosen. Also, the same employee may not be chosen twice or more.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。