15b.c

   1 #include <stdio.h>
   2 #include <limits.h>
   3 #include <uthash.h>
   4
   5 #define MFAC 5
   6
   7 struct point { int x; int y; };
   8 #define pnt(px, py) ((struct point){.x=(px), .y=(py)})
   9 struct q { struct point key; UT_hash_handle hh; };
  10 int dist[100*MFAC][100*MFAC];
  11
  12 int grid[100][100] = {0};
  13 int maxx = 0;
  14 int maxy = 0;
  15
  16 int get_grid(int x, int y)
  17 {
  18         int r = grid[y%maxy][x%maxx] + y/maxy + x/maxx;
  19         if (r > 9)
  20                 return r % 9;
  21         return r;
  22 }
  23
  24 int qcmp(const void *l, const void *r)
  25 {
  26         const struct q *lp = (const struct q *)l;
  27         const struct q *rp = (const struct q *)r;
  28         return dist[lp->key.y][lp->key.x]-dist[rp->key.y][rp->key.x];
  29 }
  30
  31 int main()
  32 {
  33         int c, x = 0;;
  34         while ( (c = getchar()) != EOF) {
  35                 if (c == '\n') {
  36                         maxx = x;
  37                         x = 0;
  38                         maxy++;
  39                 } else {
  40                         grid[maxy][x++] = c-'0';
  41                 }
  42         }
  43
  44         struct q *q = NULL;
  45
  46         for (int y = 0; y<maxy*MFAC; y++) {
  47                 for (int x = 0; x<maxx*MFAC; x++) {
  48                         dist[y][x] = INT_MAX;
  49                         struct q *i = malloc(sizeof(struct q));
  50                         i->key = pnt(x, y);
  51                         HASH_ADD(hh, q, key, sizeof(struct point), i);
  52                 }
  53         }
  54         dist[0][0] = 0;
  55         HASH_SRT(hh, q, qcmp);
  56
  57         while (q != NULL) {
  58                 struct point u = q->key;
  59                 HASH_DELETE(hh, q, q);
  60                 for (int dy = -1; dy <= 1; dy++) {
  61                         for (int dx = -1; dx <= 1; dx++) {
  62                                 //Skip diagonal neigbours
  63                                 if (abs(dx) == abs(dy))
  64                                         continue;
  65                                 //check if v is in Q
  66                                 struct q *v;
  67                                 HASH_FIND(hh, q, &pnt(u.x+dx, u.y+dy), sizeof(struct point), v);
  68                                 if (v == NULL)
  69                                         continue;
  70                                 //Update dist if necessary
  71                                 int alt = dist[u.y][u.x] + get_grid(v->key.x, v->key.y);
  72                                 if (alt < dist[v->key.y][v->key.x]) {
  73                                         dist[v->key.y][v->key.x] = alt;
  74                                         //Reinsert with in correct position
  75                                         HASH_DELETE(hh, q, v);
  76                                         HASH_ADD_INORDER(hh, q, key, sizeof(struct point), v, qcmp);
  77                                 }
  78                         }
  79                 }
  80         }
  81
  82         printf("%d\n", dist[maxy*MFAC-1][maxx*MFAC-1]);
  83 }