Rambler's Top100
 

Задача «Конструирование из блоков»

Единичным кубом назовём куб 1*1*1, вершины которого имеют целочисленные кординаты x, y, z. Два единичных куба могут образовывать новый объект путём соединения их по грани. Кубоидом назовём непустое соединение единичных кубов (см. рисунок 1). Объём кубоида равен количеству единичных кубов, из которых он составлен. Блоком назовём кубоид с объёмом не больше четырёх. Скажем, что два блока имеют одинаковый тип, если один может быть получен из другого с помощью вращений и сдвигов блока (заметьте, что отражения делать запрещено). Всего существует 12 типов блоков (см. рисунок 2). Цвета объектов на рисунке изображены лишь для иллюстрации структуры объектов, и они не несут никакой смысловой нагрузки.

Набор кубоидов D назовём декомпозицией кубоида S, если объединение всех кубоидов из D равно S, и никакой единичный куб из кубоида S не принадлежит одновременно двум разным кубоидам из D.

Напишите программу, которая по заданному описанию типов блоков и кубоида S определяет наименьший по количеству элементов набор блоков, являющийся декомпозицией кубоида S. Вам нужно выдать только типы этих блоков. Каждый тип должен быть выведен столько раз, сколько блоков этого типа встречается в декомпозиции.

Положение единичного куба в пространстве будем задавать с помощью целочисленных координат x, y, z такой его вершины, для которой сумма x+y+z минимальна.

Входной файл с описанием типов блоков имеет имя TYPES.IN. Содержимое этого файла одинаково для всех тестов. Файл содержит описание всех 12 блоков, изображённых на рисунке 2, отсортированных по номеру типа. Каждый из блоков описывается группой идущих друг за другом строк следующим образом. Первая строка состоит из целого числа I, идентифицирующего тип блока (1 £ I £ 12). Вторая строка содержит объём V блока (1 £ V £ 4). Далее следуют V строк, описывающих положение единичных кубов, из которых состоит блок. Каждая из этих V строк состоит из трёх целых чисел x, y, z (1 £ xy£ 4). Входной файл, описывающий кубоид, имеет имя BLOCK.IN. Первая строка файла содержит объём V кубоида (1£V£50). Следующие V строк описывают положение единичных кубов, из которых состоит кубоид. Каждая из этих V строк состоит из трёх целых чисел x, y, z (1 £x, y, z £ 7).

Выходной файл имеет имя BLOCK.OUT. Первая строка файла содержит одно целое число M, которое равно количеству блоков в минимальном наборе, являющимся декомпозицией заданного кубоида. Вторая строка содержит список номеров типов блоков, содержащихся в наборе. Номера могут идти в любом порядке. В случае существования нескольких решений выведите только одно из них.

 

 

 

Пример ввода и вывода.

 Подпись:  

 

Подпись: Замечание
1.	1.      Входной файл BLOCK.IN описывает кубоид «лошадь», изображённый на рисунке 1.
2.	2.      Все остальные варианты содержимого второй строки выходного файла, описывающей типы используемых блоков, приведены ниже:
2  7  10  11  12
2  7  11  11  12
4  4   7   10  11
4  4   9   10   11
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 Рисунок1. Кубоид «Лошадь»

 

 

 

 

Рисунок 1. Кубоид «Лошадь»

 
 Задача на «перебор с возвратом». Требуется найти все укладки кубоида блоками и выбрать минимальную укладку по количеству блоков. С логической точки зрения она простая, с точки зрения программной реализации – сложная. Сложность заключается в выборе структур данных для описания задачи таких, чтобы программный код был простым и ясным. Естественно, что при отсутствии опыта решения таких задач, сделать ее в отведенное время не реально.

Как обычно, решение состоит из трех частей: ввода, перебора вариантов и вывода результатов. При вводе из блока каждого типа путем поворотов строятся его модификации. Перебор вариантов укладки кубоида осуществляется как исходными блоками, так и их модификациями. При этом в кубоиде выбирается кубик с наименьшим количеством соседей (кубиков, имеющих общую грань). Затем получаем все блоки, в которых он может присутствовать. Исключаем используемый блок из дальнейшего рассмотрения, при этом корректируется количество соседей у оставшихся кубиков.

Ниже по тексту приводится прокомментированный (достаточно полно) текст оттестированного решения. Потраченное Вами время на разбор решения окупится умением решать этот интересный класс олимпиадных задач по информатике.

Вверх

{$A+,B-,D-,E-,F-,G+,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-,Y-}

{$M 56384,0,655360}

{.$R+,S+,Q+,L+,I+,D+}

{$DEFINE USETIME}

Program Task_Block;

Const

types = 'types.in';

block = 'block.in';

out = 'block.out';

CntDir = 6;{* Максимальное количество соседей.*}

MaxTime = 18*90;{*Максимальное время работы.*}

MaxBlock = 12;{*Количество различных типов блоков.*}

MaxLen = 4; {* Максимальная длина блока.*}

MaxCo = 7;{* Максимальное значение координаты.*}

MaxCntBlock = MaxBlock*30;{* Общее количество модификаций блоков.*)

MaxV = 50;{* Максимальное количество кубиков.*}

Dd : Array [1..3,1..6] Of Shortint ={*Приращения для поиска соседей*}

((0,0,1,0,0,-1),

(0,1,0,0,-1,0),

(1,0,0,-1,0,0));

Type

TSS = Set Of 0..MaxV;

TPoint = Array [1..3] Of Integer;{* Координаты кубика.*}

TDir = Array [1..CntDir] Of Byte;{*Cоседи: слева, справа, снизу, сверху, впереди и сзади. *}

TPP = Record

cc: TPoint; {* Координаты.*}

num: Integer; {* Порядковый номер.*}

dir: TDir; {* Соседи.*}

NBl: Byte; {* Номер блока, которому принадлежит кубик.*}

CDir: Byte; {* Количество соседей.*}

End;

TBlock = Record

number, len: Integer;

cc: Array [1..MaxLen] Of TPoint;

End;

TNum = Array [0..MaxLen] Of Integer;

Var

inf, ouf : Text;

AllBlk: Array [2..MaxLen,1..MaxCntBlock] Of TBlock;{*Все модификации блоков.*}

CntBlk : Array [1..MaxLen] Of Integer; {* Количества модификаций длины i.*}

Blk: Array [0..MaxV] Of TPP; {* Кубоид.*}

Bst, V : Integer; {*Количество блоков в наилучшем решении.*}

BT, Now: Array [0..MaxV] Of TNum;{*Лучшее и текущее решения.*}

All: Array [-1..MaxCo+1, 0..MaxCo+1, -1..MaxCo+1] Of Integer;

{$IFDEF USETIME}

Timer : Longint Absolute $0000:$046C;

 

Time : Longint;

{$ENDIF}

Function RavPoint(a,b: TPoint): Boolean;{*Проверка совпадения кубиков.*}

Var i: Integer;

Begin

RavPoint := False;

For i := 1 To 3 Do If a[i] <> b[i] Then Exit;

RavPoint := True;

End;

Function RavBlk(Const a,b: TBlock): Boolean;{*Проверка совпадения блоков.*}

Var i,j: Integer;

Begin

RavBlk := False;

If a.len = b.len Then Begin

For i := 1 To a.len Do Begin

j := 1;

While (j <= a.len) And Not RavPoint(a.cc[i],b.cc[j]) Do inc(j);

If j = a.len+1 Then Exit;

End;

RavBlk := True;

End;

End;

Procedure PrepareBlk(Var b: TBlock);{* «Приведение» блокауменьшение координат.*}

Var i, j, t: Integer; p: TPoint;

Begin

With b Do For i := 1 To 3 Do Begin

t := MaxInt;

For j := 1 To len Do If cc[j,i] < t Then t := cc[j,i];

For j := 1 To len Do Dec(cc[j,i],t);

End;

End;

Procedure AddBlk(Const Bl: TBlock);{*Добавление блока в массив модификаций блоков.*}

Var i: Integer;

Begin

With bl Do Begin

For i := 1 To CntBlk[len] Do

If RavBlk(Bl, AllBlk[len,i]) Then Exit;

Inc(CntBlk[len]); AllBlk[len,CntBlk[len]] := Bl;

End;

End;

Procedure RotateBlk(b: TBlock);{*Выполняем все повороты блока и «новые» блоки заносим в массив AddBlk.*}

Var i,j,k,w: Integer;

Procedure Rotate(x,y: Integer);

Var i: Integer;

p: TBlock;

Begin

p := b;

For i := 1 To b.len Do With p Do Begin

cc[i,y] := b.cc[i,x]; cc[i,x] := -b.cc[i,y];

End;

b := p;

End;

Begin

For i := 1 To 4 Do Begin

Rotate(1,2);

For j := 1 To 4 Do Begin

Rotate(1,3);

For k := 1 To 4 Do Begin

Rotate(2,3); PrepareBlk(b); AddBlk(b);

End;

End;

End;

End;

Procedure Init;{*Ввод данных. Вводятся описания блоков и строятся их модификации с помощью поворотов. Вводятся данные по кубоиду и строится его описание. *}

Var i,j,r: Integer;

bl: TBlock;

Begin

{$IFDEF USETIME}

Time := Timer;

{$ENDIF}

Assign(inf, types); Reset(inf);

FillChar(All, SizeOf(All), 0); FillChar(CntBlk, SizeOf(CntBlk), 0);

For i := 1 To MaxBlock Do With bl Do Begin{*Ввод описания блоков.*}

Read(inf, number, len);

For j := 1 To len Do Read(inf, cc[j,1], cc[j,2], cc[j,3]);

If len > 1 Then RotateBlk(bl);

End;

Close(inf);

Assign(inf, block); Reset(inf); Read(inf, V);

For i := 1 To V Do With Blk[i] Do Begin{*Ввод описания кубоида.*}

Read(inf, cc[1], cc[2], cc[3]);

All[cc[1],cc[2],cc[3]] := i;

NBl := 0; CDir := 0;

End;

For i := 1 To V Do With Blk[i] Do

For j := 1 To CntDir Do Begin{*Определяем количество «соседей» и их номера.*}

Dir[j] := All[cc[1]+dd[1,j], cc[2]+dd[2,j], cc[3]+dd[3,j]];

If Dir[j] <> 0 Then Inc(CDir);

End;

Close(inf);

End;

Function GetType(Const a: TNum): Integer;{*Определяем тип блока, ибо перебор осуществляется не только по исходным блокам, но и их модификациям. Функция используется при выводе результата.*}

Var bb: TBlock;

i: Integer;

Begin

For i := 1 To a[0] Do bb.cc[i] := Blk[a[i]].cc;{*Переписываем данные по блоку.*}

bb.len := a[0];

PrepareBlk(bb);{*Приведение блока.*}

If bb.len = 1 Then GetType := 1

Else Begin

For i := 1 To CntBlk[bb.len] Do {*Количество модификаций блоков из определенного количества кубиков, например трех.*}

If RavBlk(bb,AllBlk[bb.len,i]) Then {*Проверка на совпадение блоков.*}

Begin GetType := AllBlk[bb.len,i].number; Exit End;

GetType := 0;

End;

End;

Procedure Done;{*Вывод результата.*}

Var i: Integer;

Begin

Assign(ouf, out); Rewrite(ouf);

If Bst = MaxInt Then Begin

WriteLn(ouf, V);

For i := 1 To V-1 Do Write(ouf, 1,' ');

WriteLn(ouf);

End

Else Begin{*Выводим лучший результат.*}

WriteLn(ouf, Bst);

For i := 1 To Bst Do Begin{*Количество блоков.*}

Write(ouf, GetType(BT[i]));{*Номера блоков.*}

If i < Bst Then Write(ouf,' ');

End;

End;

Close(ouf);

End;

Procedure AddNeib(num, dp: Integer);{*Изменение количества соседей.*}

Var i: Integer;

Begin

For i := 1 To CntDir Do Inc(Blk[Blk[num].Dir[i]].CDir,dp);

End;

Procedure Rec(num, cnt, NotUse: Byte);{*Параметрами переборного решения являются: num - номер текущего кубика, cnt - количество блоков в решении, NotUse - количество неиспользованных кубиков кубоида.*}

Var i,j,t,ci,min: Byte;

Begin

Inc(Now[cnt,0]);

Now[cnt,Now[cnt,0]] := num;

Blk[num].Nbl := cnt; {*Помечаем кубик как задействованный.*}

AddNeib(num, -1);{*Уменьшаем на 1 количество соседей.*}

{$IFDEF USETIME}

If Timer-Time >= MaxTime Then Done;{*Отсечение по времени решения.*}

{$ENDIF}

If cnt+((NotUse+MaxLen-1) div MaxLen) <= Bst Then {*Отсечение. Если количество блоков в решении, плюс количество возможных дополнений, меньше лучшего из найденных решений, то продолжаем эту «ветку» перебора.*}

If NotUse=0 Then Begin Bst := cnt; BT := Now End

Else Begin

If Now[cnt,0] in [1..MaxLen-1] Then

For i := 1 To Now[cnt,0] Do

For j := 1 To CntDir Do Begin {*Цикл по соседям.*}

t := Blk[Now[cnt,i]].Dir[j];

If (Blk[t].NBl = 0) And (t <> 0) Then

Rec(t,cnt,NotUse-1);

End;

min := CntDir+1;{*Включаем в решение новый блок.*}

For i := 1 To V Do With Blk[i] Do{*Выбираем кубик кубоида с минимальным количеством соседей.*}

If (NBl = 0) And (CDir < min) Then Begin min := CDir; ci := i End;

Rec(ci,cnt+1,NotUse-1);

End;

AddNeib(num, 1);{*Выход из рекурсии. Восстанавливаем количество соседей и т. д.*}

Blk[num].NBl := 0;

Dec(Now[cnt,0]);

End;

Procedure Solve;

Begin

Bst := MaxInt;

FillChar(Now, SizeOf(Now), 0);

Now[0,0] := MaxLen-1;

Rec(0,0,V);

End;

Begin

Init; Solve; Done;

End.

 

Вверх

Белорусский рейтинг MyMinsk.com Сайты беларуси Регистр "ЗУБР" Каталог на TIGA.BY, а также  новости, работа, объявления, фото и многое другое Рейтинг@Mail.ru Rambler's Top100 Белорусский каталог программ Faststart - рейтинг сайтов, каталог интернет ресурсов, счетчик посещаемос­ти Яндекс.Метрика
Hosted by uCoz