DWITE '11 R4 #1 - Crossword Count

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
DWITE, January 2012, Problem 1

Once upon a time, humans entertained themselves by non-electronic means, and crosswords flourished as a form of entertainment. Crosswords are rectangular grids with white and black squares. They look like this:

12
3
4

Given the layout of a crossword grid, we wish to count the number of "across" words and "down" words. Now, let's define a word:

  • A word is a sequence of at least 2 adjacent white squares that lie on the same horizontal ("across") or vertical ("down") line.
  • A word must not be contained completely within another word. That is, there must be no white squares available to extend the word in either direction.

In the example above, there are 3 "across" words (starting at numbers 1, 3, and 4) and 2 "down" clues (starting at numbers 1 and 2).

The input will contain 5 test cases. Each test case will begin with two integers, denoting H and W respectively, the height and width of the grid. Neither dimension will exceed 100. H lines will follow, each consisting of W characters, describing the layout of the grid, where # represents a black square and . represents a white square.

The output will contain 5 lines of output, each containing 2 space-separated integers: the number of "across" words and the number of "down" words.

Sample Input

5 5
#....
#.#.#
.....
#.#.#
....#
2 3
...
...

Sample Output

3 2
2 3

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.