Palabras felices en una matriz X26212

Statement

html

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.

Public test cases

Input

4 7
::-)"-"
"|(-|"|
|-:-v|v
:-))"vv

9 7
^-:-)-)
||((-:|
"(-:)-"
||-^:-)
vv-|"|"
:-)"|v|
"-:-)-"
":"(-:|
(-:-)-v

8 3
(^:
"|"
:-)
v"v
^|v
:-)
||v
v":

8 1
^
|
"
^
|
"
|
v

4 9
":""-):-)
"-|:^)|-"
|(-:|-)-|
v:(-:-:-)

10 2
"^
|^
^^
|"
"|
"v
||
v^
||
v"

9 3
^^"
^^"
|||
""v
"^"
^||
|"v
"|"
v-"

9 1
"
"
|
v
v
"
|
v
v

2 8
:(-::-):
::-(-:-:

6 5
"(:-^
||:-|
v^")"
^|"^^
|"|||
"((-:

3 3
(-:
|||
:-)

5 3
"-:
|-:
^-^
|||
"-"

9 5
:-^:^
(-:""
^^""|
""||v
||-v:
vv:-)
|||""
"""|v
(-(v:

9 9
(-:::-)-"
(-:|^:-))
"|(-|"^:|
|:-)"-)""
^-))v^"||
|^((-:vv^
^(-^"":^|
|"-||-:|"
"-::v-:""

2 1
"
-

4 2
"^
||
v"
v"

1 4
(:-)

3 1
"
|
v

2 5
(-(-:
(-:-)

6 8
(-:(-:-^
"||^(-:|
|"v:-:^"
v(-:(-||
|v(:(-:v
:-):-):v

Output

Information

Author: PRO1
Language: Spanish
Translator
Original language: Catalan
Other languages: Catalan English
Official solutions: C++
User solutions: C++