WC '17 Contest 4 J4 - Efficiency

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type
Woburn Challenge 2017-18 Round 4 - Junior Division

An invasion of Earth is underway, marking the beginning of the Infinity War! Thanos has dispatched a legion of cybernetically enhanced Chitauri soldiers to a field in rural America, ordering them to stand by for further instructions. As luck would have it, the Avengers' expert archer Hawkeye happens to be standing in the same field! Though perhaps he's not so lucky after all, as he's only stocked with a single arrow.

Looking at the field from above, it can be represented as a grid with rows and columns , aligned with the four cardinal directions (North/East/South/West). The contents of each of the grid's cells can then be represented by one of three characters:

• H: Hawkeye's location
• C: A Chitauri soldier's location
• .: Empty space

Note that the grid contains exactly one H.

Thinking quickly, Hawkeye has realized that he'll need to be as efficient as possible with his single arrow. He can choose to fire it in a straight line from his location, exactly in one of the four cardinal directions (North, East, South, or West). Upon releasing the arrow, it will travel through all of the cells in the chosen direction until it reaches the edge of the field, even freely passing through (and killing) any Chitauri soldiers along the way.

Assuming that Hawkeye chooses the best cardinal direction to fire his arrow in, what's the largest number of Chitauri soldiers which he can kill?

Input Specification

The first line of input consists of two space-separated integers, and .
lines follow, the -th of which consists of characters representing the -th row of the grid, for .

Output Specification

Output a single integer, the maximum number of Chitauri soldiers which Hawkeye can kill.

Sample Input

4 5
.CCC.
C....
C.CHC
..C..

Sample Output

2

Sample Explanation

Hawkeye will kill two soldiers if he fires his arrow to the West.