Учитывая состояние квадратной сетки Игры Жизни, определите, могла ли она эволюционировать из какого-либо предыдущего состояния или могла быть только создана. То есть, определить, является ли штат «райским садом» .

вход

Квадратная сетка состояний, где 1 означает «живой», а 0 - «мертвый». Вы можете выбрать любые два различимых символа вместо 0 и 1, если хотите.

Длина стороны сетки не будет нулевой, но может быть любым натуральным числом 1 <= N <= 20.

Любая или все ячейки вне входной сетки могут быть живы в этом поколении, и любая или все из них, возможно, были живы в предыдущем поколении. Рассматриваемая вселенная бесконечна, поэтому нет граничных условий. Края входа не являются краями вселенной. В частности, сетка не переносится.

Входные данные могут быть в форме строки с разделителями строк или одной строки. Если вы хотите, вы можете взять длину стороны или площадь сетки в качестве дополнительного ввода (до или после сетки).

Допустимые форматы ввода:

010,101,010

010101010

010
101
010
3 010101010

Выход

«Создан», если нет возможного предыдущего состояния (включая состояния, большие, чем входная сетка), которое привело бы к входному состоянию в следующем поколении.

«Развивается», если существует хотя бы одно возможное предыдущее состояние (включая состояния, большие, чем входная сетка), которое привело бы к входному состоянию в следующем поколении.

При желании вы можете использовать любые две различимые строки или числа вместо «Создано» и «Развито».

Обратите внимание, что возможное предыдущее состояние не обязательно должно отличаться от ввода. Если государство имеет себя в качестве следующего поколения, то оно должно рассматриваться как развитое.

Контрольные примеры

010
101
010 Evolved

0101110100
0010101001
1011100110
0101111101
1001001111
1111001001
1011111010
0110011101
1001010100
0010111010 Created

Созданный контрольный пример взят со страницы игры жизни Ахима Фламменкампа .

Заметка

Спасибо Trichoplax за написание этого задания, и я принял его отсюда

Java - 1254 байта - очень плохое решение

import java.util.Arrays;
public class z{
static boolean u=1>0,v=0<1;
public static void main(String[] a){
int y=a.length,x=a[0].length();Boolean[][] l=new Boolean[x][y];for(int i=0;i<a.length;i++){l[i]=m(a[i]);}
Boolean[] n=new Boolean[x*y];for(int i=0;i<n.length;i++){n[i]=v;}
while(n.length==x*y){Boolean[][] o=new Boolean[x][y];for(int i=0; i<n.length;i++){o[i%x][i/x]=n[i];}
n=p(n);o=q(o,x,y);int r=0;for(int i=0;i<x*y;i++){if(o[i%x][i/x]&&l[i%x][i/x])r++;}
if(r==x*y){System.out.println("evolved");return;}}System.out.println("created");}
public static Boolean[][] q(Boolean[][] o,int bx,int by){Boolean[][] s=new Boolean[bx][by];for(int x=0; x<bx; x++){for(int y=0;y<by;y++){
int t=0;for(int tx=-1;tx<2;tx++){for(int ty=-1;ty<2;ty++){if(ty+y<0||ty+y>by-1||tx+x<0||tx+x>bx-1)continue;if(o[tx+x][ty+y]){t++;}}}
if(t>1&&t<4){s[x][y]=u;}else{s[x][y]=v;}}}return s;}
public static Boolean[] p(Boolean[] b){boolean w=u;Boolean[] x=new Boolean[b.length];for(int i=0;i<b.length;i++){if(w&&b[i]){x[i]=u;w=u;}else if(b[i]||w){x[i]=u;w=v;}else{x[i]=v;w=v;}
}if(w){x=Arrays.copyOf(x,x.length+1);x[x.length]=u;}return x;}
public static Boolean[] m(String s){Boolean[] x=new Boolean[s.length()];for(int i=0;i<s.length();i++){x[i]=s.charAt(i)=='1';}return x;}}

Требуется ввод через командную строку.

Что оно делает

Здесь нет хитростей, просто решение грубой силы. Он проходит каждую возможную начальную доску размером X, Y и повторяет ее один раз через алгоритм Game of Life и проверяет ее по входной доске. Это занимает ОЧЕНЬ много времени, так как каждая доска размером x от y имеет 2 ^ (x * y) возможных комбинаций. Потребовалось почти 10 минут, чтобы запустить доску 4х5. Глупо глупо за то, что проще, чем есть.

Если возможно, что это была усовершенствованная доска, она печатает «развитая», а если она не могла быть развита, она печатает «созданная».