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