#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 grid[SIZE][SIZE];

/* prototypes */

void compute_grid (void);
int step_compute_grid (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, previous;

  for (i = 0; i < SIZE; i++)
  {
    for (j = 0; j < SIZE; j++)
    {
      if (((i + 2*j) % 7) == 0) grid[i][j] = UNREACHABLE;
      else grid[i][j] = INFINITY;
    }
  }
  centerx = SIZE/2;
  centery = SIZE/2;

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

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

  grid[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 (grid[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 (grid[i][j] == UNREACHABLE) continue;
      if (grid[i][j] > maxval) maxval = grid[i][j];
    }
  }
  return (maxval);
}



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

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

  return (minval);
}


void
compute_grid (void)
{
  while (step_compute_grid());
}


void
print_grid (void)
{
  int i, j;

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

int
step_compute_grid (void)
{
  int changes = 0;
  int i, j, ip1, jp1, delta;

  for (i = 0; i < SIZE; i++)
  {
    for (j = 0; j < SIZE; j++)
    {
      if (grid[i][j] == UNREACHABLE) continue;
      ip1 = i + 1;
      jp1 = j + 1;
      if (ip1 < SIZE && grid[ip1][j] != UNREACHABLE)
      {
        delta = grid[ip1][j] - grid[i][j];
        if (delta > 1)
        {
          grid[ip1][j] = grid[i][j] + 1;
          changes++;
        }
        if (delta < -1)
        {
          grid[i][j] = grid[ip1][j] + 1;
          changes++;
        }
      }
      if (jp1 < SIZE && grid[i][jp1] != UNREACHABLE)
      {
        delta = grid[i][jp1] - grid[i][j];
        if (delta > 1)
        {
          grid[i][jp1] = grid[i][j] + 1;
          changes++;
        }
        if (delta < -1)
        {
          grid[i][j] = grid[i][jp1] + 1;
          changes++;
        }
      }
      if (ip1 < SIZE && jp1 < SIZE && grid[ip1][jp1] != UNREACHABLE)
      {
        delta = grid[ip1][jp1] - grid[i][j];
        if (delta > 1)
        {
          grid[ip1][jp1] = grid[i][j] + 1;
          changes++;
        }
        if (delta < -1)
        {
          grid[i][j] = grid[ip1][jp1] + 1;
          changes++;
        }
      }
    }
  }
  return (changes);
}


void
check_grid (void)
{
  int i, j;

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