15a.c

   1 #include <stdio.h>
   2 #include <stdbool.h>
   3 #include <limits.h>
   4 #include <string.h>
   5
   6 #define min(a, b) ((a) < (b) ? (a) : (b))
   7
   8 int grid[100][100] = {0};
   9 int maxx = 0;
  10 int maxy = 0;
  11
  12 int cache[100][100];
  13 int minimal_risk(int x, int y)
  14 {
  15         //check bounds
  16         if (x < 0 || y < 0 || x >= maxx || y >= maxy)
  17                 return -1;
  18         //check cache
  19         if (cache[y][x] != -1)
  20                 return cache[y][x];
  21         //Calculate
  22         int d = minimal_risk(x, y+1);
  23         int r = minimal_risk(x+1, y);
  24         if (d == -1 && r == -1) {
  25                 printf("shouldn't happen\n");
  26                 return -1;
  27         } else if (d == -1) {
  28                 cache[y][x] = r + grid[y][x];
  29         } else if (r == -1) {
  30                 cache[y][x] = d + grid[y][x];
  31         } else {
  32                 cache[y][x] = min(d, r) + grid[y][x];
  33         }
  34         return cache[y][x];
  35 }
  36
  37 int main()
  38 {
  39         int c, x = 0;;
  40         while ( (c = getchar()) != EOF) {
  41                 if (c == '\n') {
  42                         maxx = x;
  43                         x = 0;
  44                         maxy++;
  45                 } else {
  46                         grid[maxy][x++] = c-'0';
  47                 }
  48         }
  49         grid[0][0] = 0;
  50         for (int y = 0; y<maxy; y++)
  51                 for (int x = 0; x<maxx; x++)
  52                         cache[y][x] = -1;
  53         cache[maxy-1][maxx-1] = grid[maxy-1][maxx-1];
  54
  55         printf("%d\n", minimal_risk(0, 0));
  56 }