The dark of the moon is no longer a secret. The Decepticon’s leader Megatron has captured the teleportation device comprising of the pillars. These pillars, when specially oriented, form a space bridge which can be used to bring back their lost planet- “Cybertron”. But the pillars can only be controlled and operated by Sentinel Prime. He is a technology inventor who can alone operate the teleportation device. For the sake of their lost planet, both have joined hands to bring back their planet Cybertron. However the pillars should be arranged in a particular order to commence teleportation.
The pillars are of number n that should be placed in n × n grid. The pillars are placed at random in the squares of the grid, at most one pillar per square. In a single move, any single pillar can move into an unoccupied location one unit horizontally or vertically in the grid. This is done to create a “teleportation wall,” i.e., to line up all n pillars in a straight line either horizontally, vertically, or diagonally. However, Sentinel wants that Optimus prime should not know about any of these activities so he asks Megatron to place pillars using the fewest number of moves.
The input consists of multiple cases. Each case begins with a line containing an integer n (where n is the number of pillars), 1 ≤ n ≤ 15. The next line contains the row and column numbers of the first pillar, followed by the row and column numbers of the second pillar, and so on. Rows and columns are numbered as in the above diagram.
For each input case, display the case number (1, 2,…) followed by the minimum number of moves needed to line up the n pillars into a straight-line wall. Follow the format shown in the sample
Input: 5 1 2 2 4 3 4 5 1 5 3 Output: 6 Input: 5 1 1 2 1 3 1 4 1 5 1 Output: 0
|Time Limit:||0.2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions