Palabras felices en una matriz X26212

Implementad un programa que lee matrices de caracteres de entrada, y escribe el número de subpalabras felices contenidas en cada matriz.

Una subpalabra feliz es una ocurrencia (dentro de la matriz) de alguna de estas submatrices:

:-)

(-:

"
|
v

^
|
"

Entrada

La entrada tiene varios casos. Cada caso comienza con una linea con dos naturales positivos $n,m$. Después vienen $n$ lineas con $m$ caracteres cada una, escogidos de entre {’:’,’-’,’(’,’)’,’"’,’v’,'|','^'}. Casos consecutivos están separados por una linea en blanco.

Salida

Para cada caso, el programa escribe en una linea el número de subpalabras felices de la matriz de entrada.

Observación

Evaluación sobre 10 puntos:

• Solución lenta: 5 puntos.

• Solución rápida: 10 puntos.

Entendemos como solución rápida una que es correcta, de coste lineal y capaz de superar los juegos de pruebas públicos y privados. Entendemos como solución lenta una que no es rápida, pero es correcta y capaz de superar los juegos de pruebas públicos.