Mots feliços en una matriu X26212

Statement

html

Implementeu un programa que llegeix matrius de caràcters d’entrada, i escriu el nombre de submots feliços continguts en cada matriu.

Un submot feliç és una ocurrència (dins la matriu) d’alguna d’aquestes submatrius:

:-)

(-:

"
|
v

^
|
"

Entrada

L’entrada té varis casos. Cada cas comença amb una línia amb dos naturals positius n,m. Després venen n línies amb m caràcters cadascuna, escollits d’entre {’:’,’-’,’(’,’)’,’"’,’v’,'|','^'}. Casos consecutius estan separats per una linia en blanc.

Sortida

Per a cada cas, el programa escriu en una línia el nombre de submots feliços de la matriu d’entrada.

Observació

Avaluació sobre 10 punts:

Solució lenta: 5 punts.
solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, de cost lineal i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.

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: Catalan
Other languages: English Spanish
Official solutions: C++
User solutions: C++