aoc

My solutions for the Advent of Code
git clone https://git.tronto.net/aoc
Download | Log | Files | Refs | README

17b.c (1591B)


      1 #include <stdio.h>
      2 
      3 #define M 150
      4 #define MAXE 1000000
      5 #define INF 999999999
      6 
      7 #define E 0
      8 #define N 1
      9 #define W 2
     10 #define S 3
     11 
     12 int go[4][2] = { [E] = {0, 1}, [N] = {-1, 0}, [W] = {0, -1}, [S] = {1, 0} };
     13 
     14 typedef struct { int i, j, k, s, d; } node_t;
     15 
     16 char map[M][M];
     17 int n, nq, d[M][M][4][11];
     18 node_t heap[MAXE];
     19 
     20 void swap(int i, int j) {
     21 	node_t aux = heap[i];
     22 	heap[i] = heap[j];
     23 	heap[j] = aux;
     24 }
     25 
     26 void push(node_t node) {
     27 	heap[nq] = node;
     28 	for (int k = nq++; k > 0 && heap[k].d < heap[(k-1)/2].d; k = (k-1)/2)
     29 		swap(k, (k-1)/2);
     30 }
     31 
     32 node_t pop(void) {
     33 	node_t ret = heap[0];
     34 	heap[0] = heap[--nq];
     35 	for (int k = 0, j = 0; 2*k+1 < nq; k = j) {
     36 		j = 2*k+1;
     37 		if (j+1 < nq && heap[j].d > heap[j+1].d) j++;
     38 		if (heap[k].d > heap[j].d) swap(k, j);
     39 	}
     40 	return ret;
     41 }
     42 
     43 int main() {
     44 	for (n = 0; fgets(map[n], M, stdin) != NULL; n++) ;
     45 
     46 	for (int i = 0; i < n; i++)
     47 		for (int j = 0; j < n; j++)
     48 			for (int k = 0; k < 4; k++)
     49 				for (int s = 0; s < 11; s++)
     50 					d[i][j][k][s] = INF;
     51 
     52 	push((node_t){.i = 0, .j = 0, .k = -1, .s = 0});
     53 	node_t v;
     54 	for (v = pop(); v.i != n-1 || v.j != n-1; v = pop()) {
     55 		for (int k = 0; k < 4; k++) {
     56 			if (k == v.k + 2 || k == v.k - 2) continue;
     57 			if (v.s < 4 && v.k != -1 && v.k != k) continue;
     58 			int ii = v.i+go[k][0];
     59 			int jj = v.j+go[k][1];
     60 			if (ii < 0 || jj < 0 || ii >= n || jj >= n) continue;
     61 			int ss = k == v.k ? v.s + 1 : 1;
     62 			int dd = v.d + map[ii][jj] - '0';
     63 			if (d[ii][jj][k][ss] <= dd || ss > 10) continue;
     64 			d[ii][jj][k][ss] = dd;
     65 			push((node_t){.i=ii, .j=jj, .k=k, .s=ss, .d=dd});
     66 		}
     67 	}
     68 
     69 	printf("%d\n", v.d);
     70 	return 0;
     71 }