|
{Бэк-трекинг: Задача "Города" }
{ Широко известна игра "Города". Называется какой-нибудь город, допус- }
{ тим, "Саратов". Кончается на "в", значит требуется назвать другой город, }
{ у которого в названии первая буква "в". Это может быть "Воронеж". Следу- }
{ ющий город должен начинаться на "ж" и т.д. Запрещено повторять название }
{ городов. Надо написать программу, которая из набора названий городов }
{ (все названия разные) строит цепочку максимальной длины. }
{ }
{ Входные данные: файл TOWN.IN в 1-й строке содержит количество слов в }
{ наборе. Начиная со второй строки (по одному в строке) следуют названия }
{ городов (все буквы в названиях - заглавные). }
{ }
{ Выходные данные: 1-я строка TOWN.OUT содержит длину максимальной це- }
{ почки. Начиная со второй строки идет вариант цепочки, т.е. названия (по }
{ одному в строке) городов в порядке, который требуют условия игры. }
{ }
{ Примечание: Список городов во входном файле не превышает 20. }
{ Время тестирования - 2 секунды. (Pentium) }
{ }
{ ПРИМЕР: }
{ ┌──────── TOWN.IN ──────────────┬─────────── TOWN.OUT ───────────────┐ }
{ │5 │5 │ }
{ │НОВОСИБИРСК │САМАРА │ }
{ │АСТРАХАН │АСТРАХАН │ }
{ │САМАРА │НОВОСИБИРСК │ }
{ │ВЛАДИМИР │КИРОВ │ }
{ │КИРОВ │ВЛАДИМИР │ }
{ └───────────────────────────────┴────────────────────────────────────┘ }
{--------------------------------------------------------------------------}
{$M $8000,0,$1FFFF}
program towns; { "Города". Решение А.Никитина, Самара }
const mnt = 20; { максимальное количество слов на входе }
var list,chain,store :array [1..mnt] of string; { для списка и цепочек }
numin :integer; { реальное количество слов на входе }
pc :integer; { Указатель на хвост цепочки }
ml :integer; { Длина наибольшей цепочки }
sym :char; { Первичная буква для перебора }
procedure read_data; { Начальные установки и чтение данных }
var i : integer;
begin
pc:=0; ml:=0; numin:=0;
assign(input,'TOWN.IN'); reset(input);
fillchar(chain,sizeof(chain),0);
readln(numin);
if (numin > mnt) then numin:=mnt;
for i:=1 to numin do readln(list[i]);
close(input);
end;
procedure write_results; { Запись результатов в файл }
var i : integer;
begin
assign(output,'TOWN.OUT'); rewrite(output);
writeln(ml);
if (ml > 0) then begin
for i:=1 to ml do writeln(store[i]);
end;
close(output);
end;
procedure store_chain; { Запоминаем только более длинную цепочку }
var i:integer;
begin
if (pc>ml) then begin
store:=chain;
ml:=pc;
end;
end;
{ Возвращает указатель названия по 1-й букве, 0 - такого элемента нет }
function find_next_item( c:char; n:integer ):integer;
var i:integer;
begin
i:=1; find_next_item:=0;
while (i <= numin) and (n > 0) do begin
if (list[i][1]=c) then dec(n);
inc(i);
end;
if (n=0) then find_next_item:=pred(i);
end;
{ Алгоритм построения цепочек. }
procedure build_chain( c:char; n:integer ); { Метод: перебор с возвратом. }
var i:integer; { Известен как "back-tracking" }
begin
i:=find_next_item(c,n);
if (i > 0) then begin
inc(pc); chain[pc]:=list[i]; list[i][1]:='X'; { вычеркиваем }
build_chain(list[i][length(list[i])], 1);
dec(pc); list[i][1]:=c; { возвращаем }
build_chain(c, n+1);
end else store_chain;
end;
begin
read_data;
for sym:='А' to 'Я' do build_chain(sym,1);
write_results;
end.
| |