procedure ReadSet(var aFile: text; var aSet : TBoundSet);
var k : integer;
begin
while not Eoln(aFile) do begin
Read(aFile, k);
aSet:= aSet+[k];
end;
Readln (aFile);
end;
{ Глобальные переменные }
var FileIn : text; { Входной файл, полученный со спутника }
States : TStates; { Массив множеств границ }
Names : TNameSet; { Множество имен всех стран на карте }
C1, C2 : char; { Имена стран "откуда" и "куда" }
C : char; { Рабочая переменная для имен стран }
EmpireB: TBoundSet; { Границы империи }
Temp : TBoundSet; { Предыдущие границы империи }
EmpireN: TNameSet; { страны империи }
Counter: integer; { Счетчик пересечений границ (результат) }
begin {--- Главная программа ---}
{ Открываем входной файл }
Assign(FileIn, 'P_38_3.in'); Reset(FileIn);
{ Готовим цикл чтения массива множеств }
Names:=[ ]; { Названия стран }
C:= 'A'; { Первый индекс в массиве стран }
while not Eof(FileIn) do begin { Цикл чтения массива множеств }
ReadSet(FileIn, States[C]); { Чтение одного множества }
Names:= Names+[C]; { Добавляем имя страны }
C:= Succ(C); { Переход к следующей букве }
end;
Close(FileIn); { Теперь входной файл можно закрыть }
repeat { «Упрямый» цикл чтения правильных имен стран }
Write('Откуда: '); Readln(C1);
Write('Куда : '); Readln(C2);
{ Переводим имена стран в верхний регистр }
C1:= UpCase(C1); C2:= UpCase(C2);
{ Если имена не совпадают и оба достоверны, значит ввод правильный,
в таком случае выходим из цикла, а иначе повторяем ввод }
if (C1<>C2) and (C1 in Names) and (C2 in Names)
then Break
else Writeln('Ошибка! Повторите ввод имен стран');
until False;
{ Подготовка к присоединению стран }
EmpireB:= States[C1]; { Империя начинает расширяться от страны C1 }
EmpireN:= [C1]; { Здесь накапливаются имена присоединенных стран }
Counter:= 0; { Счетчик "завоевательных кампаний" }
{ Цикл, пока не будет присоединена страна C2 }
repeat
{ Подготовка к "завоевательной кампании" }
C:='A'; { Первый индекс в массиве множеств границ }
Temp:= EmpireB; { Запоминаем предыдущие границы империи }
{ Цикл очередной "завоевательной кампании" по всем странам массива }
while C in Names do begin
{ Если страна имеет общую границу, присоединяем её к империи }
if (Temp * States[C]) <> [] then begin
EmpireB:= EmpireB + States[C]; { Добавляем границы }
EmpireN:= EmpireN + [C]; { Добавляем имя страны }
end;
C:= Succ(C); { Следующий индекс в массиве множеств границ }
end; { очередная кампания завершена }
Inc(Counter); { Наращиваем счетчик "завоевательных кампаний" }
until C2 in EmpireN; { Пока не будет присоединена страна C2 }
{ Печать результата }
Writeln('Пересечений границ: ', Counter); Readln;
end.
Так была решена задача о минимальной сумме пошлин. Купцы, было, обрадовались, но вскоре явились с новым поклоном. Много ль толку от знания расходов, если не знаешь пути, по которому надо двигаться? «Сделай нам, братан, что-то типа навигатора для поиска кратчайшего пути между странами. Так, чтобы нам меньше этих пошлин платить, – умоляли купцы, – мы не поскупимся!» Ник обещал подумать, и продолжение истории следует.
Крестики-нолики
Кто не любовался яркой световой рекламой? Рекламный щит составлен из лампочек, а изображение «рисуется» их включением и отключением, – этим управляет микропроцессор. Компьютер у нас под рукой, почему бы не соорудить такой рекламный щит прямо на экране? Научим компьютер выполнять с изображением на нашем щите три действия: два зеркальных отражения (относительно горизонтальной и вертикальной осей), а также инверсию изображения (рис. 113).
Рис.113 – Операции с изображением на щите
Прежде всего, определим, как представить исходное изображение так, чтобы ввод его в компьютер был по возможности прост. Неплохим вариантом будет текстовый файл, где исходная картинка нарисована двумя символами, например, крестиком и ноликом. Присмотревшись к рис. 114, вы разглядите в правом верхнем углу изображенную таким способом букву «F».
Рис.114 – Исходный файл для представления рекламного щита, крестиками нарисована буква «F»
Размер картинки выберем таким, чтобы она помещалась на экране монитора. В текстовом режиме экран содержит 25 строк по 80 символов в каждой. Мы ограничимся 20 строками по 40 символов. Тогда воображаемая вертикальная ось нашего щита пройдет между 20-м и 21-м столбцами, а горизонтальная – между 10-й и 11- строками.
Разобравшись с видимым представлением щита, обратимся к невидимому: придумаем способ хранения в памяти «лампочек» щита. Годятся ли символьные переменные, – те же крестики и нолики? Да, но мне приглянулся способ, лучше отвечающий природе рекламного щита. Ведь каждая из лампочек может быть либо включена либо погашена, – их состояние можно отразить в булевых переменных. А сколько их понадобится? Не так уж мало – 800 штук (20 строк по 40 в каждой). Разумеется, нужен массив, но каким он будет? Предположим, что тип «рекламный щит» (Desk) объявлен так:
type TDesk = array [1..800] of Boolean;
Здесь разумеем, что первые 40 элементов массива хранят верхнюю строку щита, следующие 40 элементов, – вторую строку и так далее. Не очень удобно, правда?
Можно сделать иначе: сначала объявить отдельную строку щита TLine как массив из 40 лампочек.
type TLine = array [1..40] of Boolean;
И тогда весь щит представится массивом из 20 таких строк, – это будет массив массивов.
type TDesk = array [1..20] of TLine;
То же самое можно записать развернуто, вот так:
type TDesk = array [1..20] of array [1..40] of boolean;
Подчеркнутое означает отдельную строку щита. Паскаль разрешает собрать все индексы объявления внутри одних скобок и записать всё это ещё короче.
type TDesk = array [1..20, 1..40] of boolean;
Так мы получили структуру, которую математики называют матрицей, а программисты – двумерным массивом. Матрицы состоят из строк и столбцов. Для доступа к элементам матрицы нужны два индекса, один из которых указывает номер столбца, а другой – номер строки. Например, элемент матрицы Desk, стоящий в 5-м столбце 3-й строки, доступен так:
Desk[3, 5]
Разумеется, что для индексов позволены числовые выражения, значения которых должны лежать в объявленных пределах. При обработке матриц применяют циклы, их можно организовать как по строкам, так и по столбцам. Возьмем для примера наш рекламный щит, объявим его тип, а потом заполним значением FALSE.