#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>

#define SIZE 1024
//#define SIZE 100
#define UNREACHABLE (-2)
#define INFINITY (INT_MAX - 2)

int gridx[SIZE][SIZE]; // spostato in direzione x dal nodo della tass. esagonata
int gridy[SIZE][SIZE]; //
int gridz[SIZE][SIZE]; // spostato in direzione NE-SW dal nodo della tass. esagonata

/* prototypes */

void compute_grid (void);
int steptria (void);
int stepx (void);
int stepy (void);
int stepz (void);
void check_grid (void);
int compute_max_grid (void);
int compute_min_boundary (void);
void print_grid (void);
int count_values (int k);

/* main */

int
main (int argc, char *argv[])
{
  int i, j, k;
  int centerx, centery;
  int max_dist, min_distb;
  int countk = 0, previous;

  for (i = 0; i < SIZE; i++)
  {
    for (j = 0; j < SIZE; j++)
    {
      if (((i + j) % 3) == 0)
      {
        gridx[i][j] = UNREACHABLE;
        gridy[i][j] = UNREACHABLE;
        gridz[i][j] = UNREACHABLE;
      }
      else {
        gridx[i][j] = INFINITY;
        gridy[i][j] = INFINITY;
        gridz[i][j] = INFINITY;
      }
    }
  }
  centerx = SIZE/2;
  centery = SIZE/2;

  if (gridx[centerx][centery] == UNREACHABLE) centerx++;

  assert (gridx[centerx][centery] != UNREACHABLE);

  gridx[centerx][centery] = 0;

  //print_grid ();
  compute_grid ();
  //print_grid ();
  check_grid ();
  max_dist = compute_max_grid ();
  min_distb = compute_min_boundary ();

  printf ("Max dist = %d, min on boundary = %d\n", max_dist, min_distb);

  for (k = 0; k <= min_distb; k++)
  {
    previous = countk;
    countk = count_values (k);
    printf ("%d: %d %d\n", k, countk, countk - previous);
  }
  return (0);
}


int
count_values (int k)
{
  int i, j;
  int count = 0;

  for (i = 0; i < SIZE; i++)
  {
    for (j = 0; j < SIZE; j++)
    {
      if (gridx[i][j] == k) count++;
      if (gridy[i][j] == k) count++;
      if (gridz[i][j] == k) count++;
    }
  }
  return (count);
}



int
compute_max_grid ()
{
  int maxval = 0;
  int i, j;

  for (i = 0; i < SIZE; i++)
  {
    for (j = 0; j < SIZE; j++)
    {
      if (gridx[i][j] == UNREACHABLE) continue;
      if (gridx[i][j] > maxval) maxval = gridx[i][j];
      if (gridy[i][j] > maxval) maxval = gridy[i][j];
      if (gridz[i][j] > maxval) maxval = gridz[i][j];
    }
  }
  return (maxval);
}



int
compute_min_boundary ()
{
  int minval = INFINITY;
  int i, j;

  i = 0;
  for (j = 0; j < SIZE; j++)
  {
    if (gridx[i][j] == UNREACHABLE) continue;
    if (gridx[i][j] < minval) minval = gridx[i][j];
    if (gridy[i][j] < minval) minval = gridy[i][j];
    if (gridz[i][j] < minval) minval = gridz[i][j];
  }
  i = SIZE-1;
  for (j = 0; j < SIZE; j++)
  {
    if (gridx[i][j] == UNREACHABLE) continue;
    if (gridx[i][j] < minval) minval = gridx[i][j];
    if (gridy[i][j] < minval) minval = gridy[i][j];
    if (gridz[i][j] < minval) minval = gridz[i][j];
  }
  j = 0;
  for (i = 0; i < SIZE; i++)
  {
    if (gridx[i][j] == UNREACHABLE) continue;
    if (gridx[i][j] < minval) minval = gridx[i][j];
    if (gridy[i][j] < minval) minval = gridy[i][j];
    if (gridz[i][j] < minval) minval = gridz[i][j];
  }
  j = SIZE-1;
  for (i = 0; i < SIZE; i++)
  {
    if (gridx[i][j] == UNREACHABLE) continue;
    if (gridx[i][j] < minval) minval = gridx[i][j];
    if (gridy[i][j] < minval) minval = gridy[i][j];
    if (gridz[i][j] < minval) minval = gridz[i][j];
  }

  return (minval);
}


void
compute_grid (void)
{
  int count;

  do
  {
    count = steptria ();
    count += stepx ();
    count += stepy ();
    count += stepz ();
  } while (count);
}


void
print_grid (void)
{
  int i, j;

  for (i = 0; i < SIZE; i++)
  {
    for (j = 0; j < SIZE; j++)
    {
      printf ("%3d,%3d,%3d ", gridx[i][j], gridy[i][j], gridz[i][j]);
    }
    printf ("\n");
  }
}

int
min3 (int a, int b, int c)
{
  int minval = a;
  if (b < minval) minval = b;
  if (c < minval) minval = c;
  return (minval);
}

int
steptria (void)
{
  int changes = 0;
  int i, j, minval;

  for (i = 0; i < SIZE; i++)
  {
    for (j = 0; j < SIZE; j++)
    {
      if (gridx[i][j] == UNREACHABLE) continue;
      minval = min3 (gridx[i][j], gridy[i][j], gridz[i][j]);
      if (gridx[i][j] > minval + 1) {changes++; gridx[i][j] = minval + 1;}
      if (gridy[i][j] > minval + 1) {changes++; gridy[i][j] = minval + 1;}
      if (gridz[i][j] > minval + 1) {changes++; gridz[i][j] = minval + 1;}
    }
  }
  return (changes);
}

int stepx (void)
{
  int changes = 0;
  int i, j;

  for (i = 0; i < SIZE - 1; i++)
  {
    for (j = 0; j < SIZE; j++)
    {
      if (((i + j)%3) != 1) continue;  // triangolo di tipo A
      assert (gridx[i][j] != UNREACHABLE);
      assert (gridx[i+1][j] != UNREACHABLE);
      if (abs (gridx[i][j] - gridx[i+1][j]) <= 1) continue;
      /* differenza > 1 tra due nodi adiacenti orizzontalmente */
      changes++;
      if (gridx[i][j] > gridx[i+1][j])
        gridx[i][j] = gridx[i+1][j] + 1;
       else
        gridx[i+1][j] = gridx[i][j] + 1;
    }
  }
  return (changes);
}

int stepy (void)
{
  int changes = 0;
  int i, j;

  for (i = 0; i < SIZE; i++)
  {
    for (j = 0; j < SIZE - 1; j++)
    {
      if (((i + j)%3) != 1) continue;  // triangolo di tipo A
      assert (gridy[i][j] != UNREACHABLE);
      assert (gridy[i][j+1] != UNREACHABLE);
      if (abs (gridy[i][j] - gridy[i][j+1]) <= 1) continue;
      /* differenza > 1 tra due nodi adiacenti verticalmente */
      changes++;
      if (gridy[i][j] > gridy[i][j+1])
        gridy[i][j] = gridy[i][j+1] + 1;
       else
        gridy[i][j+1] = gridy[i][j] + 1;
    }
  }
  return (changes);
}

int stepz (void)
{
  int changes = 0;
  int i, j;

  for (i = 1; i < SIZE; i++)
  {
    for (j = 1; j < SIZE; j++)
    {
      if (((i + j)%3) != 1) continue;  // triangolo di tipo A
      assert (gridz[i][j] != UNREACHABLE);
      assert (gridz[i-1][j-1] != UNREACHABLE);
      if (abs (gridz[i][j] - gridz[i-1][j-1]) <= 1) continue;
      /* differenza > 1 tra due nodi adiacenti obliquamente */
      changes++;
      if (gridz[i][j] > gridz[i-1][j-1])
        gridz[i][j] = gridz[i-1][j-1] + 1;
       else
        gridz[i-1][j-1] = gridz[i][j] + 1;
    }
  }
  return (changes);
}


void
check_grid (void)
{
  int i, j;

  for (i = 0; i < SIZE; i++)
  {
    for (j = 0; j < SIZE; j++)
    {
      assert (gridx[i][j] < INFINITY);
      assert (gridy[i][j] < INFINITY);
      assert (gridz[i][j] < INFINITY);
    }
  }
}