hobble.c

   1 /*
   2  *              The Hobbling Horse Problem
   3  *
   4  *              (c) 1996 Martin Mares, <mj@atrey.karlin.mff.cuni.cz>
   5  */
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include <sys/time.h>
  11
  12 #define MAX 35
  13
  14 signed char dist[MAX][MAX][2];
  15
  16 signed char queue[15*MAX*MAX];
  17
  18 int M, N, x0, y0, x1, y1;
  19
  20 struct delta { int dx, dy; };
  21
  22 struct delta king[] = { {-1,-1}, {0,-1}, {1,-1}, {-1,0}, {1,0}, {-1,1}, {0,1}, {1,1} };
  23 struct delta horse[] = { {-1,-2}, {-1,2}, {-2,-1}, {2,-1}, {-2,1}, {2,1}, {1,-2}, {1,2} };
  24
  25 void
  26 fill(void)
  27 {
  28   int qr, qw, x, y, z, k, xx, yy, rho;
  29   struct delta *d;
  30
  31   memset(dist, 99, sizeof(dist));
  32   queue[0] = x0;
  33   queue[1] = y0;
  34   queue[2] = 0;
  35   dist[x0][y0][0] = 0;
  36   qr = 0;
  37   qw = 3;
  38   while (qr < qw)
  39         {
  40           x = queue[qr++];
  41           y = queue[qr++];
  42           z = queue[qr++];
  43           if (z)
  44                 {
  45                   d = king;
  46                   k = sizeof(king) / sizeof(struct delta);
  47                 }
  48           else
  49                 {
  50                   d = horse;
  51                   k = sizeof(horse) / sizeof(struct delta);
  52                 }
  53           rho = dist[x][y][z] + 1;
  54           z = !z;
  55           while (k--)
  56                 {
  57                   xx = x + d->dx;
  58                   yy = y + d->dy;
  59                   if (xx >= 0 && xx < M && yy >= 0 && yy < N && dist[xx][yy][z] > rho)
  60                         {
  61                           dist[xx][yy][z] = rho;
  62                           queue[qw++] = xx;
  63                           queue[qw++] = yy;
  64                           queue[qw++] = z;
  65                         }
  66                   d++;
  67                 }
  68         }
  69 }
  70
  71 void
  72 bug1(void)
  73 {
  74   int qr, qw, x, y, z, k, xx, yy, rho;
  75   struct delta *d;
  76
  77   memset(dist, 99, sizeof(dist));
  78   queue[0] = x0;
  79   queue[1] = y0;
  80   dist[x0][y0][0] = 0;
  81   qr = 0;
  82   qw = 2;
  83   while (qr < qw)
  84         {
  85           x = queue[qr++];
  86           y = queue[qr++];
  87           rho = dist[x][y][0] + 1;
  88           z = rho & 1;
  89           if (!z)
  90                 {
  91                   d = king;
  92                   k = sizeof(king) / sizeof(struct delta);
  93                 }
  94           else
  95                 {
  96                   d = horse;
  97                   k = sizeof(horse) / sizeof(struct delta);
  98                 }
  99           while (k--)
 100                 {
 101                   xx = x + d->dx;
 102                   yy = y + d->dy;
 103                   if (xx >= 0 && xx < M && yy >= 0 && yy < N && dist[xx][yy][0] > rho)
 104                         {
 105                           dist[xx][yy][0] = rho;
 106                           queue[qw++] = xx;
 107                           queue[qw++] = yy;
 108                         }
 109                   d++;
 110                 }
 111         }
 112 }
 113
 114 void
 115 draw(void)
 116 {
 117   int i,j,k,l;
 118
 119   for(i=0; i<N; i++)
 120         {
 121           for(j=0; j<M; j++)
 122                 {
 123                   k = dist[j][i][0];
 124                   l = dist[j][i][1];
 125                   if (k > l)
 126                         k = l;
 127                   printf("%3d", k);
 128                 }
 129           putchar('\n');
 130         }
 131 }
 132
 133 int
 134 dlt(int a, int b)
 135 {
 136   if (a < b)
 137         return b-a;
 138   else
 139         return a-b;
 140 }
 141
 142 void
 143 checkpath(int lim)
 144 {
 145   int x,y,d;
 146
 147   x = x0;
 148   y = y0;
 149   d = 0;
 150   for(;;)
 151         {
 152 //        printf("%d %d\n", x, y);
 153           if (dist[x][y][0] > d++)
 154                 {
 155                   printf("BUG: %dx%d: %d.%d->%d.%d\n", M, N, x0, y0, x1, y1);
 156                   exit(1);
 157                 }
 158           if (dlt(x, x1) <= lim && dlt(y, y1) <= lim)
 159                 break;
 160           if (dlt(x, x1) > dlt(y, y1))
 161                 {
 162                   if (x < x1)
 163                         x += 2;
 164                   else if (x > x1)
 165                         x -= 2;
 166                   else if (x >= M/2)
 167                         x -= 2;
 168                   else
 169                         x += 2;
 170                   if (y < y1)
 171                         y++;
 172                   else if (y > y1)
 173                         y--;
 174                   else if (y >= N/2)
 175                         y--;
 176                   else
 177                         y++;
 178                 }
 179           else
 180                 {
 181                   if (y < y1)
 182                         y += 2;
 183                   else if (y > y1)
 184                         y -= 2;
 185                   else if (y >= N/2)
 186                         y -= 2;
 187                   else
 188                         y += 2;
 189                   if (x < x1)
 190                         x++;
 191                   else if (x > x1)
 192                         x--;
 193                   else if (x >= M/2)
 194                         x--;
 195                   else
 196                         x++;
 197                 }
 198 //        printf("%d %d\n", x, y);
 199           if (dist[x][y][1] > d++)
 200                 {
 201                   printf("BUG: %dx%d: %d.%d->%d.%d\n", M, N, x0, y0, x1, y1);
 202                   exit(1);
 203                 }
 204           if (dlt(x, x1) <= lim && dlt(y, y1) <= lim)
 205                 break;
 206           if (x < x1)
 207                 x++;
 208           else if (x > x1)
 209                 x--;
 210           if (y < y1)
 211                 y++;
 212           else if (y > y1)
 213                 y--;
 214         }
 215 }
 216
 217 int
 218 main(void)
 219 {
 220   int i;
 221
 222   srand(time(NULL));
 223
 224 #if 1
 225   for(i=0; i<100000; i++)
 226         {
 227           M = 2 + rand() % 5;
 228           N = 3 + rand() % 5;
 229           x0 = rand() % M;
 230           y0 = rand() % N;
 231           x1 = rand() % M;
 232           y1 = rand() % N;
 233           printf("\n %dx%d: %d.%d->%d.%d\n", M, N, x0, y0, x1, y1);
 234           fill();
 235           draw();
 236           checkpath(2);
 237         }
 238 #else
 239   M = 30;
 240   N = 30;
 241   x0 = 13;
 242   y0 = 14;
 243   fill();
 244   draw();
 245 #endif
 246
 247   return 0;
 248 }