17a.c (1537B)
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][4]; 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 < 4; 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 int ii = v.i+go[k][0]; 58 int jj = v.j+go[k][1]; 59 if (ii < 0 || jj < 0 || ii >= n || jj >= n) continue; 60 int ss = k == v.k ? v.s + 1 : 1; 61 int dd = v.d + map[ii][jj] - '0'; 62 if (d[ii][jj][k][ss] <= dd || ss > 3) continue; 63 d[ii][jj][k][ss] = dd; 64 push((node_t){.i=ii, .j=jj, .k=k, .s=ss, .d=dd}); 65 } 66 } 67 68 printf("%d\n", v.d); 69 return 0; 70 }