Czech Technical University in Prague
ICPC Foundation
Czech ACM Chapter
Central Europe Regional Contest 2018
Matrice
matrice.c, matrice.cpp, Matrice.java, matrice.py
Agent Sue Thomas and her son are looking for trinities in a grid. The word trinity is a neologism
referring to a particular triangular (as the morpheme "tri" suggests) shape composed of cells in
the grid.
Each trinity is a result of taking a square-shaped area of the cells and removing all cells that
lie either above or below one of the two diagonals of the area. The diagonal may be either the
main diagonal (southeast-northwest direction) or the main antidiagonal (southwest-northeast
direction). A valid trinity consists of at least three grid cells and all its cells contain the same
character.
Input Specification
The first input line contains two numbers N and M (1 ≤ N, M ≤ 1000), describing the number
of rows and columns in the grid, respectively. Each of next N lines contains M characters,
whose ASCII codes are between 33 and 126, inclusively.
Output Specification
Output the number of different valid trinities in the input grid.
Sample Input 1
Output for Sample Input 1
22
1
AA
Ad
Output for Sample Input 2
Sample Input 2
60
55
#####
####.
###..
##...
#....
Output for Sample Input 3
Sample Input 3
0
54
hwwr
eahe
lroy
lswo
oaau
Output for Sample Input 4
Sample Input 4
7
56
#girls
##areb
#.#est
#..#!!
#####!
