26881a36f382ce7caa96ed2a5045b07a8c3d48ee
7 struct point
{ int x
; int y
; };
8 #define pnt(px, py) ((struct point){.x=(px), .y=(py)})
9 struct q
{ struct point key
; UT_hash_handle hh
; };
10 int dist
[100*MFAC
][100*MFAC
];
12 int grid
[100][100] = {0};
16 int get_grid(int x
, int y
)
20 int r
= grid
[y
%maxy
][x
%maxx
] + y
/maxy
+ x
/maxx
;
26 int qcmp(const void *l
, const void *r
)
28 const struct q
*lp
= (const struct q
*)l
;
29 const struct q
*rp
= (const struct q
*)r
;
30 return dist
[lp
->key
.y
][lp
->key
.x
]-dist
[rp
->key
.y
][rp
->key
.x
];
36 while ( (c
= getchar()) != EOF
) {
42 grid
[maxy
][x
++] = c
-'0';
48 for (int y
= 0; y
<maxy
*MFAC
; y
++) {
49 for (int x
= 0; x
<maxx
*MFAC
; x
++) {
51 struct q
*i
= malloc(sizeof(struct q
));
53 HASH_ADD(hh
, q
, key
, sizeof(struct point
), i
);
57 HASH_SRT(hh
, q
, qcmp
);
60 struct point u
= q
->key
;
61 HASH_DELETE(hh
, q
, q
);
62 for (int dy
= -1; dy
<= 1; dy
++) {
63 for (int dx
= -1; dx
<= 1; dx
++) {
64 //Skip diagonal neigbours
65 if (abs(dx
) == abs(dy
))
69 HASH_FIND(hh
, q
, &pnt(u
.x
+dx
, u
.y
+dy
), sizeof(struct point
), v
);
72 //Update dist if necessary
73 int alt
= dist
[u
.y
][u
.x
] + get_grid(v
->key
.x
, v
->key
.y
);
74 if (alt
< dist
[v
->key
.y
][v
->key
.x
]) {
75 dist
[v
->key
.y
][v
->key
.x
] = alt
;
76 HASH_DELETE(hh
, q
, v
);
77 HASH_ADD_INORDER(hh
, q
, key
, sizeof(struct point
), v
, qcmp
);
83 printf("%d\n", dist
[maxy
*MFAC
-1][maxx
*MFAC
-1]);