Mason's Mark
Time limit4sMemory limit512 MB
Count the stones carrying each of three mason's marks A, B, and C in a noisy black and white photo of a wall.
- Level
Medium7 of 10
- Topics
- Matrix, Graph, Implementation
- Solved
- No attempts yet
Problem
A mason's mark is a symbol often found on dressed stones in buildings and other public structures. As Peter walks with his camera through Paris, he notices these marks on the wall of the Tour JeanSans-Peur. Every stone has one of the marks A, B or C, which are quite visible. He makes a black and white photo and observes:
- The picture shows stones, and every stone contains exactly one mark.
- All marks have one of the following shape with and being arbitrary strictly positive integers, and possibly different for each mark. Marks are surrounded by white pixels, and marks cannot be rotated.

- The picture contains some noise, which are black pixels surrounded by 8 white pixels.
- There are 3 kinds of black pixels, corresponding respectively to the noise, the mason's marks, and the region around the stones.
- Every white pixel belongs to the surface of a stone, and some of them also belong to the interior of a mark.
- The white pixels belonging to the surface of the same stone but not belonging to the interior of the mark are all connected with respect to vertical and horizontal adjacency. The surface of a stone may be non-convex.
- The black pixels of the region around the stones are connected with respect to vertical, horizontal, diagonal, and anti-diagonal adjacency. You can go from any black pixel of the region around the stones to any other such pixel by moving from one pixel to one of its eight adjacent pixels. All pixels of the border of the picture are black and belong to this region.
Input
The first line contains two integers and . The next lines each contain a string of length . The strings are composed of . and #. A # character represents a black pixel and a . character represents a white pixel.
Output
The output should consist of a single line with three integers , , and separated by single spaces, indicating the number of stones with the respective marks A, B, and C.
Constraints
;
.