/* Problem 6--Triangles
   At first glance, I thought this was the hardest problem.  After doing
   it, I no longer think this.  I think this was very reasonable.  This
   solution counts isosceles triangles and computes equilaterals as an
   equilateral is two isosceles's pasted together. */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MIN(a,b) ((a)<(b)?(a):(b))

int main (int argc, char **argv);
int Read (void);
int CountIsos (int i, int j, int v, int h);
void Process (void);

FILE *in, *out;
int sz; /* size of letter matrix */
char **M; /* letter matrix */
int L[26], total; /* number of each kind of triangle, and the total ct*/

int main (int argc, char **argv) {

  int i=0;

 in = fopen ("prob6.in","r");
 out = fopen ("prob6.out","w");
 while (Read ()) { /* Read in a letter matrix */
  Process (); /* Count triangles */
  fprintf (out,"(%d) ",total);
  for (i=0;i<26;i++) /* If a letter ct is -1, that means it didn't */
   if (L[i]!=-1) fprintf (out,"%d %c ",L[i],i+'A'); /* appear */
  fprintf (out,"\n");
  for (i=0; i < sz; i++) free (M[i]);
  free (M);
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Read gets the next data set.  It returns 0 if the data is exhausted,
   1 otherwise. */
int Read (void) {

  int i, j;

 fscanf (in,"%d",&sz); /* get matrix size */
 fgetc (in); /* get eoln character */
 if (sz==0) return 0;
 memset (L,-1,sizeof L); /* Initialize L to -1's */
 M = malloc (sz*sizeof (char *));
 for (i=0; i < sz; i++) { /* Read in matrix characters */
  M[i] = malloc (sz);
  for (j=0; j < sz; j++) {
   fscanf (in,"%c",&M[i][j]);
   L[M[i][j]-'A'] = 0;
  }
  fgetc (in); /* get eoln character */
 }
 total = 0;
 return 1;
}

/* CountIsos accepts a position in the matrix and a vertical and
   horizontal direction and returns the number of isosceles triangles
   with that corner extending in that direction. */
int CountIsos (int i, int j, int v, int h) {

  int ct = 0, lev = 1, ok, k;
  /* ct is the number of triangles found.  lev is the size of triangle
     currently sought. */

 while (1) {
  if (i+v*lev >= sz) break; /* We're done if the matrix is too small */
  if (i+v*lev < 0) break;   /* the triangle. */
  if (j+h*lev >= sz) break;
  if (j+h*lev < 0) break;
  ok = 1;
  for (k=0; ok && k <= lev; k++) /* Check whether this diagonal */
   ok = M[i+(lev-k)*v][j+k*h] == M[i][j]; /* matches the corner */
  if (!ok) break;
  L[M[i][j]-'A']++; /* If so, add another triangle! */
  total++;
  ct++;
  lev++;
 }
 return ct;
}

/* Process counts the number of triangles in a given data set. */
void Process (void) {

  int i, j, a, b, c, d, eq;

 for (i=0; i < sz; i++)
  for (j=0; j < sz; j++) {
   a = CountIsos (i,j,1,1);  /* For each position in the matrix, count*/
   b = CountIsos (i,j,1,-1); /* the isosceles triangles cornered there*/
   c = CountIsos (i,j,-1,1);
   d = CountIsos (i,j,-1,-1); /* The equilateral triangles can be */
   eq = MIN(a,b) + MIN(a,c) + MIN(b,d) + MIN(c,d); /* found by pasting*/
   L[M[i][j]-'A'] += eq; /* isosceles triangles together */
   total += eq;
  }
}