Клеточки

1. Клеточки. Входной файл: cellular.in. Выходной файл: cellular.out. Квадратное поле поделено на nхn клеток. Каждая клетка может находиться в одном из двух состояний: 0 и 1. В определенных интервалах, называемых генерациями, все клетки меняют своё состояние одновременно, в зависимости от того, в каком состоянии они и их соседи были в предыдущей генерации. Внутренние клетки имеют по 4 соседа, угловые имеют по 2 соседа, а все остальные по три. Один из возможных путей изменения состояния клетки – это посмотреть на сумму её состояния и состояния соседних клеток. Новое состояние клетки будет определяться в зависимости от этой суммы по определенному правилу. В данном случае правило обновления клеток может быть закодировано 6 битами. Например, правило 001001 означает, что новое состояние каждой клетки равно:
• 0, если сумма была равна 5
• 0, если сумма была равна 4
• 1, если сумма была равна 3
• 0, если сумма была равна 2
• 0, если сумма была равна 1
• 1, если сумма была равна 0,
где под суммой подразумевается сумма «старых» состояний клеток и их соседей. Мы можем использовать бинарный код для уникального определения правила. 6 – ти битное число abcdef соответствует десятичному числу, равному (a * 32) + (b * 16) + (с * 8) + (d * 4) + (е * 2) + (f * 1). Вышеописанное правило (001001) соответствует числу 9.
Например, если n = 4 мы можем иметь начальные состояния
1111
1111
1111
1111
По правилу 9 после одной генерации состояние будет:
1001
0000
0000
1001
После второй генерации
0000
0110
0110
0000
Имея размер n, количество генерации g, начальное состояние s и конечное состояние е, вы должны определить правило с минимальным соответствующим десятичным числом, которое генерирует конечное состояние е из начального состояния s ровно после g генераций. Первая строка входного файла состоит из двух целых чисел n и g разделенных пробелом, определяющих размер поля и количество генераций. Каждая из следующих n строк состоит из n цифр, каждое из которых либо 0, либо 1. Эти n строк определяют начальное состояние s. Следующая строка пустая. Следующие n строк определяют конечное состояние е. оно представлено в том же виде, что и начальное состояние. Выходной файл должен состоять только из одного целого числа, которое определяет минимальное десятичное число, которое соответствует правилу, генерирующему е из s ровно через g генераций.
Пример
cellular.in
4 2
1111
1111
1111
1111
0000
0110
0110
0000
cellular.out
9
Технические ограничения:
n<=30
g<=50

0