INFOMAN брой 17
{ This is the input data:
1 1 1
0 1 0 0 1
0 1 0 0 1
0 0 1 1 1
0 0 0
-----------------------
Игра с 21 квадратчета
-----------------------
Имаме игрална дъска сас следната форма:
X X X
X X X X X
X X X X X
X X X X X
X X X
Всяко поле (означено на фугурата с "X") може или да или 0 или 1. Върху дъс-
ката можем да прилагаме 3 вида операции - инвертиране на 9 полета разполо-
жени във формата на квадрат 3x3; инвертиране на 5 полета разположени във
формата на кръстче; инвертиране на всички полета. Инвериране наричаме про-
маня на поле по следния начин: 0 става 1, а 1 става 0. Да се напише програ-
ма, която при зададена крайна дъска (описана като 21 числа) намира минимал-
ния брой операции от 3-те посочени вида, чрез които от дъска, запълнена ця-
лата с 0 се стига до дадената крайна дъска. Да се опчечата -1 ако няма ре-
шение. Ето и един пример:
0 0 0 0 0 0 1 0 0
0 0 0 0 0 оп. 1 0 0 1 1 1 оп. 2 1 1 0 1 1
0 0 0 0 0 -------> 0 0 1 1 1 -------> 0 1 1 1 1
0 0 0 0 0 0 0 1 1 1 0 0 1 1 1
0 0 0 0 0 0 0 0 0
(фиг. 1) (фиг. 2) (фиг. 3)
Ако е дадена дъската от фиг. 3, тя може да се получи от началната (фиг.1)
с 2 хода, както е показано на схемата.
РЕШЕНИЕ: Общ принцип при тези задачи е че никоя операция не трябва да се
прилага повече от веднъж и че редът на операциите нама значение. Да порас-
съждаваме малко над задачата:Операция 1 може да се приложи точно на 5 мес-
та, операция 2 - точно на 9 места, а операция 3 - точно на 1 място.Понеже
не трябва да прилагаме никоя операция повече от веднъж и редът няма значе-
ние, то за всяка операция от разгледаните 5+9+1 = 15 има две възможности:
или да бъде приложена или да не бъде приложена. Да номерираме операциите
с числата 1,2,..,15. Всички евентуално различни дъски, които могат да се
получат се получават като се приложи произволно подмножество на множество-
то от 15-те операции [1,2,...15]. Както знаем броят на подмножествата на
N-елементно множество е 2^N. Ето защо всички дъски които могат да се полу-
чат са само 32768 (2^15),като евентуално някои от тях могат да са еднакви.
Идеята за решаване на задачата е да се генерират тези 32768 дъски и да се
провери дали някоя от тях не съвпада с търсената. Ако никоя не съвпада,ня-
ма решение. Ако съвпадат повече от 1, то решение е тази дъска, която е по-
лучена с минимален брой операции.
Относно конкретната реализация на описания алгоритъм ще споменем, че
дъската се пази като масив от 21 числа,а 15-те операции като константи от
по 21 числа - битова маска на полетата, които трябва да инвертира съответ-
ната операция.Всички подмножества на 15-елементно множество генерираме по
стандартен алгоритъм - с 1 цикъл от 0 до 2^15-1. В този цикъл всяко число
ни определя еднозначно едно подмножество от операции и това число съответ-
ства точно на двоичното представяне на числото. Ако k-тия бит на числото
е 1, то трябва да извършим k-тата операция, а ако е 0, k-тата операция не
се извършва. Ако искаме да възстановим самите операции, които водят до ре-
шението е необходимо просто когато прилагаме една операция да я записваме
в някакъв списък по подходящ начин.
Интересно е да се знае и още един правилен, макар и по-бавен алгоритъм
за решаване на задачата. Да забравим за горните разсъждения. Понеже дъска-
та е от 21 полета, всяко от които е или 0 или 1,то всички конфигурации ко-
ито могат да се получат са точно 2^21. Да си направим булев масив P,в кой-
то си отбелязваме дали една конфугурация е била вече получена.Такъв булев
масив можем да си направим като използваме 256 KB памет (по 1 бит за все-
ки елемент). Тогава следния алгоритъм решава задачата.
P[0] = 1; P[1..2^21-1] = 0;
for turn = 1 to endlessness
NewObtained = false
for i = 0 to 2^21-1
if P[i] then
T = NumberToBoard(i);
for op = 1 to 15
NewT = MakeOperation(op,T);
if NewT = DestinationBoard
PrintSolution(turn); Exit;
if P[ BoardToNumber(NewT) ] = 0 then
P[ BoardToNumber(NewT) ] = 1
NewObtained = true
if NewObtained = false then
NoSolution
Понеже сме номерирали конфигурациите с числата от 0 до 2^21-1, можем да
кажем, че конфигурация 0 се получава за 0 хода.Идеята на алгоритъма е да
получим първо всички конфигурации, които могат да се получат за 1 ход и
да ги маркираме в масива P. След това от всяка получена до момента конфи-
гурация получаваме всички възможни,които могат да се получат от нея и ги
маркираме в P. Така получаваме в P всички конфигурации,които могат да се
получат за 0, 1 или 2 хода. На следващата стъпка получаваме всички конфи-
гурации, които се получават за 0, 1, 2 или 3 хода и т.н. Когато стигнем
в ситуация, при която не сме получили нито една нова конфигурация, то ня-
ма смисъл да продължаваме. Ако търсената не е намерена до момента, то ре-
шение няма.
16.03.2000
Светлин Наков
(автор на задачата)
}
{$R-,S-,Q-}
CONST InFileName = 'GAME21.PAS';
OutFileName = '';
Type TGame = array[1..21] of byte;
VAR Dest: TGame;
Procedure ReadData; { Read the input data - Dest }
Var F:Text;
i: integer;
ch: char;
Begin
Assign(F,InFileName); Reset(F);
for i:= 1 to 21 do
begin
Read(F,ch); while (ch <>'0') and (ch<>'1') do Read(F,ch);
if ch='0' then Dest[i]:=0 else Dest[i]:=1;
end;
Close(F);
End;
Function Correct(bitmask:longint): boolean;
{ This apply the operations given in the bitmask upon the 0-filled board
and returns if the obtained board is the board we are looking for /Dest/ }
Const Operation: array[1..15] of TGame =
(
{ squares shapes}
(1,1,1,0,1,1,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0), {1,2,3,5,6,7,10,11,12}
(0,0,0,1,1,1,0,0,1,1,1,0,0,1,1,1,0,0,0,0,0), {4,5,6,9,10,11,14,15,16}
(0,0,0,0,1,1,1,0,0,1,1,1,0,0,1,1,1,0,0,0,0), {5,6,7,10,11,12,15,16,17}
(0,0,0,0,0,1,1,1,0,0,1,1,1,0,0,1,1,1,0,0,0), {6,7,8,11,12,13,16,17,18}
(0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1,1,0,1,1,1), {10,11,12,15,16,17,19,20,21}
{ chryst shapes}
(1,0,0,1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0), {1,4,5,6,10}
(0,1,0,0,1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0), {2,5,6,7,11}
(0,0,1,0,0,1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0), {3,6,7,8,12}
(0,0,0,0,1,0,0,0,1,1,1,0,0,0,1,0,0,0,0,0,0), {5,9,10,11,15}
(0,0,0,0,0,1,0,0,0,1,1,1,0,0,0,1,0,0,0,0,0), {6,10,11,12,16}
(0,0,0,0,0,0,1,0,0,0,1,1,1,0,0,0,1,0,0,0,0), {7,11,12,13,17}
(0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,0,0,1,0,0), {10,14,15,16,19}
(0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,0,0,1,0), {11,15,16,17,20}
(0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,0,0,1), {12,16,17,18,21}
{ whole the space shape}
(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1) {1,2,....,20,21}
);
Var T: TGame;
i,op: integer;
Begin
for i:= 1 to 21 do T[i]:=0;
for op:= 1 to 15 do
if bitmask and (1 shl (op-1)) <> 0 then
for i:= 1 to 21 do {apply operation op}
T[i]:=T[i] xor Operation[op][i];
for i:= 1 to 21 do
if T[i] <> Dest[i] then
begin Correct:=false; Exit; end;
Correct:=true;
End;
Function CountOfBits(bitmask:longint): integer;
{ Return the count of bits 1 in the binary represantation of bitmask }
Var bits: integer;
Begin
bits:=0;
repeat
if odd(bitmask) then inc(bits);
bitmask:= bitmask div 2;
until bitmask = 0;
CountOfBits:= bits;
End;
Procedure Solve;
Var OutF: Text;
Best: integer;
i: longint;
Begin
{ Find the solution. There are only 32768 configurations to check }
Best:=MaxInt;
for i:= 0 to (1 shl 15)-1 do
if Correct(i) then
if CountOfBits(i) < Best then
Best:=CountOfBits(i);
{ Print the found solution }
Assign(OutF,OutFileName); Rewrite(OutF);
if Best <> MaxInt then WriteLn(OutF,Best)
else WriteLn(OutF,-1);
Close(OutF);
End;
BEGIN
ReadData;
Solve;
END.