#arc0064. [arc006_4]アルファベット探し

[arc006_4]アルファベット探し

訂正:任意の整数に拡大した形も同じ形である→任意の正の整数に拡大した形も同じ形であるに訂正させて頂きました。

问题描述

高桥君被朋友出了这样一个谜题。
首先,给定如图1所示的由白色和黑色组成的7行7列(共49个格子)的图形A,B,CA,B,C

图1:给定的A,B,CA,B,C形状

在给定的图形中,回答A,B,CA,B,C各有多少个。给定的图中的黑色格子都是A,B,CA,B,C中的一部分,除了A,B,CA,B,C之外不会出现其他图形。但是,A,B,CA,B,C被认为是可以任意放大为正整数倍的形状,并且放大后的形状被视为相同。因此,图2(a)中的3个AA都被计为一个AA。另外,如图2(b)所示,形状也可以旋转9090度。

图2(a):AA被放大为2倍、3倍的例子   图2(b):旋转的AA的例子

注意,A,B,CA,B,C的形状还包括周围的白色格子,图3中显示了构成AA的7行7列和另一个图形BB重叠的情况是不会出现的。

图3:不会作为输入提供的其他图形重叠的例子

从给定的图形中,请回答A,B,CA,B,C各自有多少个。


输入

输入从标准输入中按以下格式给出。HH WW c(0,0)c(0,1)c_{(0,0)}c_{(0,1)} ‥‥ c(0,W1)c_{(0,W-1)} c(1,0)c(1,1)c_{(1,0)}c_{(1,1)} ‥‥ c(1,W1)c_{(1,W-1)} : : c(H1,0)c(H1,1)c_{(H-1,0)}c_{(H-1,1)} ‥‥ c(H1,W1)c_{(H-1,W-1)}

  • 输入共有H+1H+1行。
  • 第一行包含两个整数H(1H1,000)H(1≤H≤1,000)W(1W1,000)W(1≤W≤1,000),分别表示给定图的行数和列数。
  • 接下来的HH行描述了图的状态c(i,j)(0iH1,c_{(i,j)}(0≦i≦H-1, 0jW1)0≦j≦W-1)
    • i+2i+2行第j+1j+1个字符c(i,j)c_{(i,j)}是字符.o,表示第i+1i+1行第j+1j+1列格子的状态:
      • .:表示该格子是白色的。
      • o:表示该格子是黑色的。
    • 图中只有A,B,CA,B,C,没有其他形状。
    • A,B,CA,B,C的形状不会重叠。

输出

在标准输出上以A,B,CA,B,C的顺序以空格分隔输出给定图中存在的AA的个数、BB的个数和CC的个数。
注意,这也包括了任意正整数倍放大的形状和旋转9090度的形状。
最后要输出换行。


输入例子1


7 7
.......
...o...
..o.o..
.o...o.
.ooooo.
.o...o.
.......

输出例子1


1 0 0
  • 存在一个AA,没有BBCC

输入例子2


7 14
..............
.oooo....oooo.
.o...o..o...o.
.oooo....oooo.
.o...o..o...o.
.oooo....oooo.
..............

输出例子2


0 2 0
  • 存在一个正常方向的BB和一个旋转180180度的BB,所以有两个BB

输入例子3


14 42
..........................................
.................o...o........o.o.........
....oooooo.......ooooo.......o.o.o........
....oooooo.......o...o.......o.o.o........
..oo......oo......o.o........o.o.o........
..oo......oo.......o.........ooooo........
..oo......................................
..oo......................................
..oo......oo............ooo...............
..oo......oo...........o...o..............
....oooooo.............o...o..............
....oooooo.............o...o..............
........................o.o...............
..........................................

输出例子3


1 1 2
  • 存在旋转180180度的AA,逆时针旋转9090度的BB,顺时针旋转9090度的CC,以及放大为22倍的CC

输入例子4


6 8
........
........
........
........
........
........

输出例子4


0 0 0
  • 没有A,B,CA,B,C

输入例子5


40 40
........................................
..ooo.....o.................ooo.........
.o...o...o.o....oooo.......o.o....o.o...
.o......o...o..o...o......o..o...o...o..
.o...o..ooooo...oooo.......o.o...o...o..
..ooo...o...o..o...o........ooo..o...o..
................oooo..............ooo...
........................................
...........................o.o..........
..........................o.o.o.........
.........ooo..............o.o.o.........
........o...o.............o.o.o.........
..ooo...o...o..ooooo......ooooo.........
.o...o..o...o..o.o.o....................
.....o...o.o...o.o.o..............o.o...
.o...o.........o.o.o.............o.o.o..
..ooo...........o.o..............o.o.o..
.................................o.o.o..
.................................ooooo..
...........................oooo.........
..........................o...o.........
...........................oooo.........
.................ooo......o...o.........
................o...o......oooo.........
..oooooo........o.......................
..oooooo........o...o...................
....oo..oo.......ooo...............oooo.
....oo..oo........................o...o.
....oo....oo.......................oooo