Условие
Игра «Жизнь» является упрощенной моделью развития колонии бактерий.
Игровое поле для этой игры представляет собой прямоугольник
M × N клеток. В начальный момент времени в некоторых клетках находятся бактерии. За один
шаг игры некоторые бактерии могут погибнуть, а некоторые родиться на
свободных клетках в соответствии со следующими правилами:
1) бактерия, у которой есть не более одной соседки, погибает «от скуки»;
2) бактерия, у которой есть более трех соседок, погибает «от тесноты»;
3) на свободной клетке, у которой есть ровно три соседние бактерии,
рождается новая бактерия.
Все эти правила применяются одновременно ко всем клеткам игрового поля.
Клетки считаются соседними, если у них есть хотя бы одна общая точка.
Напишите программу, которая:
по заданной колонии находит ее предка, то есть колонию, чьим следующим
поколением она является, либо сообщает, что это невозможно;
находит колонию, у которой нет предка, и которая погибает не ранее, чем
через L шагов, либо сообщает, что такой колонии не существует.
Входные данные
Если во входном файле записана матрица
M × N (2 ≤ M, N ≤ 15), то программа должна решать пункт 1 задачи для колонии бактерий, задаваемой этой
матрицей. Бактерии обозначаются символом *, а пустые клетки – символом
. (точка). Если во входном файле заданы три числа M, N и L (2 ≤
M, N ≤ 10, 0 ≤ L ≤ 10), то программа должна решать пункт 2 для этих параметров.
Выходные данные
Если искомая колония существует, то ее следует вывести в выходной файл в
формате, приведенном в описании входных данных к пункту 1. В противном
случае ваша программа должна записать в выходной файл сообщение «NOT POSSIBLE».
Пример входного файла для пункта 1
...
***
...
Пример выходного файла для пункта 1
.*.
.*.
.*.
Пример входного файла для пункта 2
2 2 10
Пример выходного файла для пункта 2
*.
**
Решение
Скачать архив тестов и решений
Источники и прецеденты использования
|
книга |
предмет |
информатика |
Автор |
Беров В., Лапунов А., Матюхин В., Пономарев А. |
Название |
Особенности национальных задач по информатике |
Издательство |
Триада-С |
Год издания |
2000 |
глава |
Номер |
2 |
Название |
Перебор с возвратом |
гЮДЮВЮ |
Номер |
10 |