#PU488. USACO 2014 December Contest, Bronze — Problem 2. Crosswords

USACO 2014 December Contest, Bronze — Problem 2. Crosswords

USACO 2014 December Contest, Bronze — Problem 2. Crosswords

题目描述

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..

..#

.##

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

clear cells may not be part of any clue.

样例

样例 1

5 3

...

#..

...

..#

.##
4

1 1

1 2

1 3

3 1