Игра «Жизнь»

Игра «Жизнь» была придумана английским математиком Джоном Конвейем в 1970 году. Впервые описание этой игры опубликовано в октябрьском выпуске (1970) журнала Scientic American, в рубрике «Математические игры» Мартина Гарднера.

Место действия этой игры – «вселенная» – это размеченная на клетки поверхность. Каждая клетка на этой поверхности может находиться в двух состояниях: быть живой или быть мертвой. Клетка имеет восемь соседей. Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:

• пустая (мертвая) клетка с ровно тремя живыми клетками-соседями оживает;
• если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае (если соседок меньше двух или больше трех) клетка умирает (от «одиночества» или от «перенаселенности»).

В этой задаче рассматривается игра «Жизнь» на торе. Представим себе прямоугольник размером n строк на m столбцов. Для того, чтобы превратить его в тор мысленно «склеим» его верхнюю сторону с нижней, а левую с правой.

Таким образом, у каждой клетки, даже если она раньше находилась на границе прямоугольника, теперь есть ровно восемь соседей.

Ваша задача состоит в том, чтобы найти конфигурацию клеток, которая будет через k поколений от заданного.

Входные данные

Первая строка входного файла INPUT.TXT содержит три целых числа: n, m, k (4 ≤ n, m ≤ 100; 0 ≤ k ≤ 100). Последующие n строк содержат по m символов каждая и описывают начальную конфигурацию. j-ый символ i-ой строки равен «.» (точка), если соответствующая клетка мертва, и «*» (звездочка) – если жива.

Выходные данные

В выходной файл OUTPUT.TXT выведите конфигурацию клеток через k поколений после начального в том же формате, в каком конфигурация задается во входном файле.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]