Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Игра «Жизнь»

(Время: 1 сек. Память: 16 Мб Сложность: 29%)

Игра «Жизнь» была придумана английским математиком Джоном Конвейем в 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 поколений после начального в том же формате, в каком конфигурация задается во входном файле.

Примеры

INPUT.TXTOUTPUT.TXT
1 5 5 1
**...
..**.
.*...
..*..
...*.
.*.**
*.*..
.*.*.
..*..
.**..
2 5 5 5
**...
..**.
.*...
..*..
...*.
.***.
.*...
.*...
..**.
.....
3 4 7 5
.*.*.*.
*.*.*.*
.*.*.*.
*.*.*.*
.......
.......
.......
.......

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru