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