#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); } } }