Задача «Конструирование из блоков»Единичным кубом назовём куб 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 £ x, y, z £ 4). Входной файл, описывающий кубоид, имеет имя BLOCK.IN. Первая строка файла содержит объём V кубоида (1£V£50). Следующие V строк описывают положение единичных кубов, из которых состоит кубоид. Каждая из этих V строк состоит из трёх целых чисел x, y, z (1 £x, y, z £ 7). Выходной файл имеет имя BLOCK.OUT. Первая строка файла содержит одно целое число M, которое равно количеству блоков в минимальном наборе, являющимся декомпозицией заданного кубоида. Вторая строка содержит список номеров типов блоков, содержащихся в наборе. Номера могут идти в любом порядке. В случае существования нескольких решений выведите только одно из них.
Пример ввода и вывода.
Рисунок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. |