Bessie the cow likes to solve crossword puzzles. Unfortunately, her sister Elsie has spilled milk all over her book, making it difficult to see where each clue begins. It's your job to help Bessie recover the clue numbering!

An unlabeled crossword is given to you as an N by M grid (3 <= N <= 50, 3 <= M <= 50). Some cells are clear and some are blocked. Clue numbering follows two steps:

Step 1: A cell begins a horizontal clue if it is clear, its neighboring cell to the left is blocked or outside the grid, and the two cells to its right are clear (so a horizontal clue represents a word of 3 or more characters). The rules for a vertical clue are analogous (the cell above must be blocked or outside the grid, and the two cells below must be clear).

Step 2: We assign numbers to each cell that begins a clue, sequentially starting with 1 in reading order (top row left-to-right, then the next row, etc.). Only cells beginning a clue are assigned numbers.

Note that the crossword described in the input may not satisfy constraints typically seen in published crosswords; some clear cells may not be part of any clue.

Line 1: N and M separated by a space.

Lines 2..1+N: Each describes a row of the grid with M characters, either '.' (clear) or '#' (blocked).

On the first line, the number of clues. On each remaining line, the row and column of a single clue (in the order described above). The top-left cell has position (1, 1).

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > December > Bronze