Problem B
Squares
B. Kordiemski in his book on mathematical puzzles has included
the following task:
Let's consider a square of size N x N (N<=100). The square is
filled with all the integer numbers from 1 to N*N located in
it randomly. Each position is described by its coordinates [r,
c] where r describes the row number and c is the column number
(r, c >=1). See the following figure:
4 6 9
3 8 2 (Fig. 1)
7 1 5
You have to place the numbers in the ascending order - the
final square should be as follows:
1 2 3
4 5 6 (Fig. 2)
7 8 9
In order to obtain such a result you can swap 2 positions in a
square. For instance you can swap positions [3, 2] and [1, 1]
in Fig. 1. After that you will obtain the following square:
1 6 9
3 8 2 (Fig. 3)
7 4 5
Then, you can swap another pair of positions. Each swapping is
a single move. Your goal is to determine the minimal number of
moves necessary to obtain the ascending order of numbers for a
given square. To avoid the unnecessary moves you should try to
invent a kind of swapping strategy (which pairs should be
swapped in what order).
Input
The input contains:
· N - the number of rows equal to the number of columns
· a square - sequence of integer numbers constituting the
square
Output
The output should contain the minimal number of moves necessary
to obtain the ascending order in a given square.
Suggestion
Let's consider the following square:
3 2 5
4 7 8 (Fig. 4)
1 9 6
In that case, if you want to obtain the minimal number of
swappings, you have to move numer 1 from position [3,1] to
[1,1], number 7 from [2,2] to [3,1], number 5 from [1,3] to
[2,2] and number 3 from [1,1] to [1,3].You can do it by the
following swappings:
swap [3,1 ] and [1, 1]; swap [3, 1] and [2, 2];
swap [2, 2] and [1, 3]
Another group of swappings is connected with numbers 6, 8 and
9. You have to move number 6 from [3,3] to [2,3], number 8 from
[2,3] to [3,2] and number 9 from [3,2] to [3,3]. You can do it
by swappings:
swap [2, 3] and [3, 3]; swap [3, 2] and [3,3]
(Note that, the numbers 2 and 4 remain untouched as they are
at the right positions in the input square).
Making the above 5 swappings gives you (as a result) the
ordered square and this is also the minimal number of swappings
necessary to get such a square.
EXAMPLE 1
Input
3
3 1 5
4 2 8
6 7 9
Output
Movements: 5
EXAMPLE 2
Input
4
16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1
Output
Movements: 8
Solution
Rozpatrzmy kwadrat:4 6 9
8 2 1
7 3 5
Minimalna liczba przestawien moze byc osiagnieta gdy bedziemy
zamieniali liczby wedlug nastepujacego schematu:
Zapiszmy liczby w ciagu:
liczba 4 6 9 8 2 1 7 3 5
numer pola 1 2 3 4 5 6 7 8 9
Na pozycji 1 musi byc jedynka. Zamieniamy wiec liczby 4 i 1. W
wyniku tego liczba cztery znajdzie sie na pozycji 6:
liczba 1 6 9 8 2 4 7 3 5
numer pola 1 2 3 4 5 6 7 8 9
Na tej pozycji powinna byc 6, wiec kolejna zamiana bedzie
dotyczyla
liczb 4 i 6. Czworka znajdzie sie teraz na pozycji 2:
liczba 1 4 9 8 2 6 7 3 5
numer pola 1 2 3 4 5 6 7 8 9
I tak dalej, az 4 nie znajdzie sie na pozycji 4. Wowczas
bierzemy kolejna liczbe, ktora jeszcze nie znalazla sie na
swojej pozycji i rozpoczynamy podobny ciag zamian. Kontynuujemy
tak dlugo, az wszystkie liczby znajda sie na swoich pozycjach.
W naszym przypadku otrzymujemy nastepujacy ciag zamian:
( w ogolnosci takich ciagow moze byc kilka)
4 - 1, 4 - 6, 4 - 2, 4 - 5, 4 - 9, 4 - 3, 4 - 8
W sumie: 7 zamian - i to jest nasze rozwiazanie
Zadanie zaczerpnieto z ksiazki:
B. Kordiemski " Rozrywki Matematyczne ", Wiedza Powszechna,
Warszawa 1956, wyd. I
Tests
TEST 1
input 3
4 6 9
8 2 1
7 3 5
output Movements: 7
TEST 2
input 5
7 24 10 19 3
12 20 8 22 23
2 15 25 18 13
11 21 5 9 16
17 4 14 1 6
output Movements: 19
TEST 3
input 4
16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1
output Movements: 8
TEST 4
input 3
3 1 5
4 2 8
6 7 9
output Movements: 5
TEST 5
input matrix of the size 100 x 100
output Movements: 5943
Listing
#include
int N;
int *tab;
int change(int from)
{
int i,a;
if (tab[from]==from) return 0;
for (i=0;i
© zwir, wierzej,
Mon Oct 28 23:01:26 MET DST 1996