Hidden words P92088


Statement
 

pdf   zip

thehtml

Write a program that reads a sequence of rectangular grids, and for each one prints where starts and where ends the single word that contains. If a grid does not have any word, the program must indicate it.

Input

Input consists of a series of grid descriptions separated by an empty line. Each grid starts with two natural numbers strictly positive: the number of rows n and the number of columns m. After, n rows with m characters (any space) for each one. Each grid contains, at most, a word, horizontally, vertically, or in the two diagonal directions. In this problem, a word is a non empty sequence of uppercase letters.

Output

For each grid, if contains any word, print where starts and where ends (the vertical words are from the top to the bottom; the other words are from the left to the right); otherwise, print that the grid does not contain any word. Follow the format of the instance.

Public test cases
  • Input

    4 10
    ~~~~~~~~~~
    ~CAMP~~~~~
    ~~~~~~~~~~
    ~~~~~~~~~~
    
    7 5
    (((((
    )))))
    (((((
    ))))R
    ((((I
    ))))U
    (((((
    
    6 6
    P\\\\\
    \L\\\\
    \\U\\\
    \\\J\\
    \\\\A\
    \\\\\\
    
    5 5
    11111
    1uuu1
    1uUu1
    1uuu1
    11111
    
    1 3
    res
    

    Output

    the word starts  (2, 2) and ends at (2, 5)
    the word starts  (4, 5) and ends at (6, 5)
    the word starts  (1, 1) and ends at (5, 5)
    the word starts and ends at (3, 3)
    there is not any word
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++