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:
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 file DATA1.txt will contain 5 test cases. Each test case will begin with two integers, H and W, respectively denoting 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 file OUT1.txt will contain 5 lines of output, each containing two space-separated integers: The number of “across” words and the number of “down” words.
5 5
#....
#.#.#
.....
#.#.#
....#
2 3
...
...
3 2
2 3