Острова в океане
АрхивНа одной из первых олимпиад школьников по программированию предлагалась такая задача:
Океан изображен (закодирован) матрицей NxN. Каждый остров - это "звездочка" в матрице. Задача состоит в построении карты островов только по кодированной информации о горизонтальном и вертикальном расположении островов. Чтобы проиллюстрировать этот код, рассмотрим такую "карту":
Числа слева от каждой строки показывают порядок и размеры групп островов в этих строках. Например, "1 2" в первой строке означает, что в этой строке находится группа из одного острова, за которой идет группа из двух островов с океаном произвольной длины слева и справа от каждой группы островов. Аналогичным образом последовательность "1 1 1" над первым столбцом означает, что в этом столбце находится три группы с одним островом в каждой, и т. д.
Естественно, вначале на карте нет никаких звездочек - смысл задачи и заключается в том, чтобы их расставить. Если исходные числа подобраны корректно, то расстановка звездочек, во-первых, существует, а во-вторых, может быть найдена чисто логическими рассуждениями.
Покажем, как это можно сделать для уже нарисованной выше карты. Например, можно начать с заполнения четвертого столбца.Так как там стоят числа "2 3", то в этом столбце располагаются ровно пять островов: два сверху, потом океан, потом еще три острова. Но так как высота столбца равна 6, то океан занимает в этом столбце ровно одну клетку. Таким образом, четвертый столбец уже заполнен. Дальше аналогично заполняется, скажем, пятая строка. Карта постепенно прорисовывается и приобретает такой вид:
Теперь, оказывается, последняя строка уже заполнена, и можно легко восстановить первый и последний столбцы, а затем и вторую строку. Это дает такой промежуточный результат:
Я не буду лишать читателей удовольствия самим закончить решение этой головоломки. Но все дело в том, что задача "острова в океане" - это не начало истории, а ее середина. А начало ей положил еще на пару лет раньше японец Нишио Тецуя (Tetsuya Nishio). Именно он является автором этого замечательного типа головоломок. Впервые такие задачки - Нишио назвал их paint-by-numbers - были предложены им на международном конкурсе решателей головоломок, состоявшемся в 1990 году. При этом участники состязались между собой на скорость решения серии таких задач (и естественно, на правильность). Головоломки понравились многим - и очень быстро завоевали себе место на страницах самых разных изданий, посвященных головоломкам и занимательным задачам. Печатались они и у нас - в газете "Поле Чудес" - под названием "японские кроссворды".
Вот еще две задачи из серии paint-by-numbers. Первая - 10x10, вторая - 20x25. И, как обычно, предлагаю к ним в качестве добавки сверхзадачу для любителей поупражняться в программировании. Добавка, впрочем, уже сформулирована: надо написать программу, которая сможет самостоятельно решать задачи типа "островов в океане" для больших карт. (Обратите внимание, что при картах размера 50x50 полный перебор вариантов уже потребует очень большого машинного времени, так что этот путь мне представляется тупиковым. А вот если попробовать применять различные эвристики, наподобие тех, которые использует человек при решении такой задачи, поиск решения может быть существенно упрощен и сокращен.) Желаю успехов! Пишите мне, как всегда, на kk@knop.spb.ru
