Under construction

Still being built. Things may change

Mason's Mark

Time limit4sMemory limit512 MB

Summary
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 xx and yy 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 WW and HH. The next HH lines each contain a string of length WW. 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 AA, BB, and CC separated by single spaces, indicating the number of stones with the respective marks A, B, and C.

Constraints

7≤W≤10007 \le W \le 1000;

9≤H≤10009 \le H \le 1000.

Examples1

  1. Example 1

    Input
    26 15
    ##########################
    ##........######......#..#
    #...###....#####..#......#
    #...#.#....####.........##
    #...###.....##....#####..#
    #...#.#.....#.....#####..#
    #...###.....#.....##.##..#
    #........#..#.#...#####..#
    #..###......#.....#####..#
    #..#........#...#.##.##..#
    #..#........#.....##.##..#
    #..#...#.#..#...#.##.##..#
    #..###......#............#
    ###....#....##....##.....#
    ##########################
    
    Expected output
    1 1 0