Se da una matriz de $n \times m$ formada por 0 y 1, que representa una imagen de píxeles. Debes determinar si la imagen forma el número "8".
Se considera que la imagen representa el número "8" si y solo si se cumplen las dos condiciones siguientes:
Todos los píxeles con valor
1forman exactamente una componente conexa con conectividad de cuatro vecinos.Dentro de esta componente de
1, hay exactamente dos "agujeros".Aquí, un "agujero" se define como una componente de
0con conectividad de cuatro vecinos que cumple la siguiente condición:- La componente está completamente rodeada de
1(es decir, todos sus píxeles externos adyacentes son1) y no toca en ningún punto el borde de la matriz.
- La componente está completamente rodeada de
Nota: Dos píxeles son adyacentes con conectividad de cuatro vecinos si y solo si son adyacentes en una de las cuatro direcciones: arriba, abajo, izquierda o derecha.
Entrada
La primera línea contiene dos enteros positivos $n,m$ $(1\le n,m\le 1000)$.
Las siguientes $n$ líneas contienen cada una $m$ enteros con valor 0 o 1, que describen la matriz.
Salida
Si la matriz es "8", imprime la cadena "This is eight." en una línea (sin las comillas).
Si la matriz no es "8", imprime la cadena "I don't know what this number is." en una línea (sin las comillas).
Ejemplos
Entrada 1
9 5 0 1 1 1 0 1 1 0 1 1 1 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 1 1 1 0 1 1 0 1 1 1 0
Salida 1
This is eight.
Entrada 2
5 3 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1
Salida 2
I don't know what this number is.
Entrada 3
7 7 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1
Salida 3
This is eight.