15b.c

   1 #include <stdio.h>
   2 #include <stdbool.h>
   3 #include <stdlib.h>
   4 #include <limits.h>
   5 #include <string.h>
   6 #include <search.h>
   7
   8 #define min(a, b) ((a) < (b) ? (a) : (b))
   9 #define MFAC 1
  10
  11 struct point { int x; int y; };
  12
  13 int grid[100][100] = {0};
  14 int maxx = 0;
  15 int maxy = 0;
  16
  17 int get_grid(int x, int y)
  18 {
  19         if (x == 0 && y == 0)
  20                 return 0;
  21         int r = grid[y%maxy][x%maxx] + y/maxy + x/maxx;
  22         while (r > 9)
  23                 r -= 9;
  24         return r;
  25 }
  26
  27 int dist[100*MFAC][100*MFAC];
  28
  29 int mindist(const void *l, const void *r)
  30 {
  31         struct point lp = *(const struct point *)l;
  32         struct point rp = *(const struct point *)r;
  33         return dist[rp.y][rp.x]-dist[lp.y][lp.x];
  34 }
  35
  36 struct point *is_in_q(struct point *q, size_t nq, int x, int y)
  37 {
  38         for (size_t i = 0; i<nq; i++)
  39                 if (q[i].x == x && q[i].y == y)
  40                         return q+i;
  41         return NULL;
  42 }
  43
  44 int main()
  45 {
  46         int c, x = 0;;
  47         while ( (c = getchar()) != EOF) {
  48                 if (c == '\n') {
  49                         maxx = x;
  50                         x = 0;
  51                         maxy++;
  52                 } else {
  53                         grid[maxy][x++] = c-'0';
  54                 }
  55         }
  56
  57         struct point q[100*MFAC*100*MFAC];
  58         size_t qp = 0;
  59         struct point prev[100*MFAC][100*MFAC];
  60
  61 //      grid[0][0] = 0;
  62         for (int y = 0; y<maxy*MFAC; y++) {
  63                 for (int x = 0; x<maxx*MFAC; x++) {
  64                         dist[y][x] = INT_MAX;
  65                         prev[y][x] = (struct point){.x=-1, .y=-1};
  66                         q[qp++] = (struct point){.x=x, .y=y};
  67                 }
  68         }
  69         dist[0][0] = 0;
  70
  71         while (qp > 0) {
  72 //              printf("size of q: %lu\n", qp);
  73                 qsort(q, qp, sizeof(struct point), mindist);
  74                 qp--;
  75                 struct point u = q[qp];
  76                 for (int dy = -1; dy <= 1; dy++) {
  77                         for (int dx = -1; dx <= 1; dx++) {
  78                                 //Skip diagonal neigbours
  79                                 if (dx == dy)
  80                                         continue;
  81                                 //check if v is in Q
  82                                 struct point *v = is_in_q(&q[0], qp, u.x+dx, u.y+dy);
  83                                 if (v == NULL)
  84                                         continue;
  85                                 //Update dist if necessary
  86                                 int alt = dist[u.y][u.x] + get_grid(v->x, v->y);
  87                                 if (alt < dist[v->y][v->x]) {
  88                                         dist[v->y][v->x] = alt;
  89                                         prev[v->y][v->x] = u;
  90                                 }
  91                         }
  92                 }
  93         }
  94
  95         printf("path: ");
  96         struct point u = {.y=maxy*MFAC-1, .x=maxx*MFAC-1};
  97         do {
  98                 u = prev[u.y][u.x];
  99                 printf("%d,%d ", u.x, u.y);
 100         } while (u.x!= 0 && u.y != 0);
 101
 102         printf("\n");
 103
 104         printf("%d\n", dist[maxy*MFAC-1][maxx*MFAC-1]);
 105 }