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 ~R~ rows and ~C~ columns ~(1 \le R, C \le 50)~, 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
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?
The first line of input consists of two space-separated integers, ~R~
~R~ lines follow, the ~i~-th of which consists of ~C~ characters representing the ~i~-th row of the grid, for ~i = 1 \ldots R~.
Output a single integer, the maximum number of Chitauri soldiers which Hawkeye can kill.
4 5 .CCC. C.... C.CHC ..C..
Hawkeye will kill two soldiers if he fires his arrow to the West.