USACO 2014 December Contest, Bronze

Problem 2. Crosswords

Contest has ended.

Log in to allow submissions in analysis mode

Problem 2: Crosswords [Mark Gordon, 2014] Like all cows, Bessie the cow likes to solve crossword puzzles. Unfortunately, her sister Elsie has spilled milk all over her book of crosswords, smearing the text and making it difficult for her to see where each clue begins. It's your job to help Bessie out and 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 will be clear (typically colored white) and some cells will be blocked (typically colored black). Given this layout, clue numbering is a simple process which follows two logical steps: Step 1: We determine if a each cell begins a horizontal or vertical clue. If a cell begins a horizontal clue, it must be clear, its neighboring cell to the left must be blocked or outside the crossword grid, and the two cells on its right must be clear (that is, a horizontal clue can only represent a word of 3 or more characters). The rules for a cell beginning 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 a number to each cell that begins a clue. Cells are assigned numbers sequentially starting with 1 in the same order that you would read a book; cells in the top row are assigned numbers from left to right, then the second row, etc. Only cells beginning a clue are assigned numbers. For example, consider the grid, where '.' indicates a clear cell and '#' a blocked cell. ... #.. ... ..# .## Cells that can begin a horizontal or vertical clue are marked with ! below: !!! #.. !.. ..# .## If we assign numbers to these cells, we get the following; 123 #.. 4.. ..# .## Note that crossword described in the input data may not satisfy constraints typically seen in published crosswords. For example, some clear cells may not be part of any clue. INPUT: (file The first line of input contains N and M separated by a space. The next N lines of input each describe a row of the grid. Each contains M characters, which are either '.' (a clear cell) or '#' (a blocked cell). SAMPLE INPUT: 5 3 ... #.. ... ..# .## OUTPUT: (file crosswords.out) On the first line of output, print the number of clues. On the each remaining line, print the row and column giving the position of a single clue (ordered as described above). The top left cell has position (1, 1). The bottom right cell has position (N, M). SAMPLE OUTPUT: 4 1 1 1 2 1 3 3 1
Contest has ended. No further submissions allowed.