Happy words in a matrix X26212


Statement
 

pdf   zip

html

Implement a program that reads matrices of characters from the input, and prints the number of happy subwords contained in each of those matrices.

A happy subword is an occurrence (inside the matrix) of one of these submatrices:

:-)

(-:

"
|
v

^
|
"

Input

The input has several cases. Each case begins with a line with two positive naturals n,m. Next, there are n lines with m characters each, chosen from {’:’,’-’,’(’,’)’,’"’,’v’,'|','^'}. Consecutive cases are separated by a blank line.

Output

For each case, the program prints in one line the number of happy subwords contained in the input matrix.

Observation

Grading up to 10 points:

  • Slow solution: 5 points.
  • Fast solution: 10 points.

We understand as a fast solution one which is correct, with linear cost and which passes the public and private tests. We understand as slow solution one which is not fast, but it is correct and passes the public tests.

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

    5
    13
    2
    3
    5
    4
    6
    2
    3
    5
    2
    2
    7
    12
    0
    2
    1
    1
    3
    10
    
  • Information
    Author
    PRO1
    Language
    English
    Translator
    Original language
    Catalan
    Other languages
    Catalan Spanish
    Official solutions
    C++
    User solutions
    C++