/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
縦 H マス横 W マスのグリッドがあります。グリッドの上から i 行目、左から j 列目のマスを (i, j) と呼びます。
グリッドの各マスには # と . のいずれかの文字が書かれています。(i, j) に書かれている文字を C[i][j] とします。また、整数 i, j が 1 \leq i \leq H と 1 \leq j \leq W の少なくとも一方を満たさない場合、 C[i][j] を . と定義します。
正整数 a, b, n が以下の条件を全て満たす時、(a,b) および (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n) の 4n + 1 マスを (a,b) を中心とするサイズ n のバツ印 と呼びます。
- C[a][b] は
#である。 - 1 \leq d \leq n を満たす整数 d について、 C[a+d][b+d],C[a+d][b-d],C[a-d][b+d],C[a-d][b-d] はいずれも
#である。 - C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1],C[a-n-1][b-n-1] のうち少なくとも 1 つは
.である。
例えば次の図で示された例では、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印がグリッド上にあります。
グリッドにはいくつかのバツ印があります。バツ印を構成するマス以外に # は書かれていません。
また、異なるバツ印を構成するマス同士は頂点を共有しません。以下の 2 つのグリッドは異なるバツ印を構成するマス同士が頂点を共有している例で、このようなグリッドの状態は入力として与えられません。 例えば左のグリッドでは (3, 3) と (4, 4) が頂点を共有しているのが条件に反しています。
N = \min(H, W) とします。また、サイズ n のバツ印の個数を S_n とします。S_1, S_2, \dots, S_N を計算してください。
制約
- 3 \leq H, W \leq 100
- C[i][j] は
#または. - 異なるバツ印を構成するマス同士は頂点を共有しない
- H, W は整数
入力
入力は以下の形式で標準入力から与えられる。
H W C[1][1]C[1][2]\dots C[1][W] C[2][1]C[2][2]\dots C[2][W] \vdots C[H][1]C[H][2]\dots C[H][W]
出力
S_1, S_2, \dots, S_N を空白区切りで出力せよ。
入力例 1
5 9 #.#.#...# .#...#.#. #.#...#.. .....#.#. ....#...#
出力例 1
1 1 0 0 0
問題文に書かれた説明の通り、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印が書かれています。
入力例 2
3 3 ... ... ...
出力例 2
0 0 0
バツ印が 1 個も書かれていない場合もあります。
入力例 3
3 16 #.#.....#.#..#.# .#.......#....#. #.#.....#.#..#.#
出力例 3
3 0 0
入力例 4
15 20 #.#..#.............# .#....#....#.#....#. #.#....#....#....#.. ........#..#.#..#... #.....#..#.....#.... .#...#....#...#..#.# ..#.#......#.#....#. ...#........#....#.# ..#.#......#.#...... .#...#....#...#..... #.....#..#.....#.... ........#.......#... #.#....#....#.#..#.. .#....#......#....#. #.#..#......#.#....#
出力例 4
5 0 1 0 0 0 1 0 0 0 0 0 0 0 0
Score : 300 points
Problem Statement
We have a grid with H horizontal rows and W vertical columns. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let C[i][j] be the character written on (i, j). For integers i and j such that at least one of 1 \leq i \leq H and 1 \leq j \leq W is violated, we define C[i][j] to be ..
(4n+1) squares, consisting of (a, b) and (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n, 1 \leq n), are said to be a cross of size n centered at (a,b) if and only if all of the following conditions are satisfied:
- C[a][b] is
#. - C[a+d][b+d],C[a+d][b-d],C[a-d][b+d], and C[a-d][b-d] are all
#, for all integers d such that 1 \leq d \leq n, - At least one of C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1], and C[a-n-1][b-n-1] is
..
For example, the grid in the following figure has a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).
The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because (3, 3) and (4, 4) share a corner.
Let N = \min(H, W), and S_n be the number of crosses of size n. Find S_1, S_2, \dots, S_N.
Constraints
- 3 \leq H, W \leq 100
- C[i][j] is
#or.. - No two different squares that comprise two different crosses share a corner.
- H and W are integers.
Input
The input is given from Standard Input in the following format:
H W C[1][1]C[1][2]\dots C[1][W] C[2][1]C[2][2]\dots C[2][W] \vdots C[H][1]C[H][2]\dots C[H][W]
Output
Print S_1, S_2, \dots, and S_N, separated by spaces.
Sample Input 1
5 9 #.#.#...# .#...#.#. #.#...#.. .....#.#. ....#...#
Sample Output 1
1 1 0 0 0
As described in the Problem Statement, there are a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).
Sample Input 2
3 3 ... ... ...
Sample Output 2
0 0 0
There may be no cross.
Sample Input 3
3 16 #.#.....#.#..#.# .#.......#....#. #.#.....#.#..#.#
Sample Output 3
3 0 0
Sample Input 4
15 20 #.#..#.............# .#....#....#.#....#. #.#....#....#....#.. ........#..#.#..#... #.....#..#.....#.... .#...#....#...#..#.# ..#.#......#.#....#. ...#........#....#.# ..#.#......#.#...... .#...#....#...#..... #.....#..#.....#.... ........#.......#... #.#....#....#.#..#.. .#....#......#....#. #.#..#......#.#....#
Sample Output 4
5 0 1 0 0 0 1 0 0 0 0 0 0 0 0