Problem E Hidden squares |
The typical Hidden words game can be modified to generate other problems. In particular, geometric figures can be found in them.
Given n rows and columns of capital letters, and a capital letter, we want to count the number of squares in the grid with vertices in positions in the grid where that letter appears.
The input will consist of a series of problems, with each problem in a series of lines. In the first line the dimension of the grid (n) is indicated, in the second line appears the number of letters (m) for which we want to calculate the number of squares, and in consecutive lines the n rows of letters, each row in a line, and without separation between letters in the same row. When the input of a problem finishes the next problem begins in the next line. The input finishes when 0 appears as the dimension of the grid. The number of rows of each grid is less than or equal to 100.
The solutions of the different problems are separated by a black line. For each problem in the input and each letter in the input of the problem a line is written with the letter and the number of squares for this letter, separated by a space. For example, in the grid
AAA
AAA
BAB
the squares with vertices in A are:
AA-
AA-
---
-AA
-AA
---
-A-
A-A
-A-
3
2
AAA
AAA
BAB
A
B
4
2
ABBA
BBBB
ABBB
ABBA
A
B
0
A 3
B 0
A 1
B 8