Problem D
Counting Cacti
As fun as hanging around the saloon may be, research won’t finish itself. In an attempt to survey how hazardous the desert may be, Gus has requested assistance collecting statistics about the cacti growing in different areas; of course, due to the lack of adequate technology, the counting must be based on sketches drawn by the best artist in the west, Alonzo.
The dimensions of each sketch are $r$ by $c$, they consist of a solid background represented by ‘.’, and an undetermined amount of cacti.
Alonzo drew each cactus as a simple rectangle with ‘|’ on the left and right edge, ‘-’ on the top and bottom edge, and ‘+’ in each corner. Note, some of the drawn cacti may extend past the edge of the sketch and cacti may be obscured by other cacti.
The inside of each drawn cactus may contain any amount of spines represented by ‘*’, any spot inside a cactus that is not covered by another cactus and is not a spine will be represented by a space.
By Gus’s instructions, you are to count the maximum number of visible cacti in Alonzo’s sketch. A cactus is considered visible only if part of its interior is seen in the sketch. If a cactus has multiple disjoint visible sections, count each as its own visible cactus–Gus hypothesizes that this will provide an upper bound on how many cacti may be in the desert.
Additionally, to better understand how hazardous the visible cacti are, you’ve been requested to count the largest number of visible spines on any of the visible cacti you previously counted.
Input
The first line of input contains two integers $3 \le r, c \le 250$, indicating the dimensions of a sketch.
The next $r$ lines of input make up Alonzo’s sketch, each line contains $c$ characters. Every character will be from the set (., ‘ ’, *, -, +, |), representing a part of the sketch as described above.
Output
Output in a single line, the maximum number of visible cacti in the sketch Alonzo drew, and the largest number of spines that appeared on a single visible cactus.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 7 ....... .+---+. .| * |. .|* |. .+---+. ....... |
1 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 7 ....... +-----+ |*+-+*| +-| |-+ ..+-+.. |
3 1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 49 -+ |.....| +-+.........+-+.........+-+.........+- |-+.....+-| |.........| |.........| |.........| |.........| |..+------| |...+--+..| |..+------| -+...+-+...+-+..|***** | |...| |..+-+..| +- |...| |...| |..|******| |...+--+..| |..| | |...+-+...| |..|******| |.........| |..| | -+.........| |..|******+-+...+-----| |..| +- |...+-+...| |..+------| |...| | |..+------| |...| |...| |.........| |...| | |.........| -+...| |...+-+.........+-+...+-----+-+.........+- |
20 23 |
