8 #define min(a, b) ((a) < (b) ? (a) : (b))
11 struct point
{ int x
; int y
; };
13 int grid
[100][100] = {0};
17 int get_grid(int x
, int y
)
21 int r
= grid
[y
%maxy
][x
%maxx
] + y
/maxy
+ x
/maxx
;
27 int dist
[100*MFAC
][100*MFAC
];
29 int mindist(const void *l
, const void *r
)
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
];
36 struct point
*is_in_q(struct point
*q
, size_t nq
, int x
, int y
)
38 for (size_t i
= 0; i
<nq
; i
++)
39 if (q
[i
].x
== x
&& q
[i
].y
== y
)
47 while ( (c
= getchar()) != EOF
) {
53 grid
[maxy
][x
++] = c
-'0';
57 struct point q
[100*MFAC
*100*MFAC
];
59 struct point prev
[100*MFAC
][100*MFAC
];
62 for (int y
= 0; y
<maxy
*MFAC
; y
++) {
63 for (int x
= 0; x
<maxx
*MFAC
; x
++) {
65 prev
[y
][x
] = (struct point
){.x
=-1, .y
=-1};
66 q
[qp
++] = (struct point
){.x
=x
, .y
=y
};
72 // printf("size of q: %lu\n", qp);
73 qsort(q
, qp
, sizeof(struct point
), mindist
);
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
82 struct point
*v
= is_in_q(&q
[0], qp
, u
.x
+dx
, u
.y
+dy
);
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
;
96 struct point u
= {.y
=maxy
*MFAC
-1, .x
=maxx
*MFAC
-1};
99 printf("%d,%d ", u
.x
, u
.y
);
100 } while (u
.x
!= 0 && u
.y
!= 0);
104 printf("%d\n", dist
[maxy
*MFAC
-1][maxx
*MFAC
-1]);