#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