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:
1 | 2 | |||
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 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 "across" words (starting at numbers , , and ) and "down" clues (starting at numbers and ).
The input will contain 5 test cases. Each test case will begin with two integers, denoting and respectively, the height and width of the grid. Neither dimension will exceed . lines will follow, each consisting of 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