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
)
18 int r
= grid
[y
%maxy
][x
%maxx
] + y
/maxy
+ x
/maxx
;
24 int qcmp(const void *l
, const void *r
)
26 const struct q
*lp
= (const struct q
*)l
;
27 const struct q
*rp
= (const struct q
*)r
;
28 return dist
[lp
->key
.y
][lp
->key
.x
]-dist
[rp
->key
.y
][rp
->key
.x
];
34 while ( (c
= getchar()) != EOF
) {
40 grid
[maxy
][x
++] = c
-'0';
46 for (int y
= 0; y
<maxy
*MFAC
; y
++) {
47 for (int x
= 0; x
<maxx
*MFAC
; x
++) {
49 struct q
*i
= malloc(sizeof(struct q
));
51 HASH_ADD(hh
, q
, key
, sizeof(struct point
), i
);
55 HASH_SRT(hh
, q
, qcmp
);
58 struct point u
= q
->key
;
59 HASH_DELETE(hh
, q
, q
);
60 for (int dy
= -1; dy
<= 1; dy
++) {
61 for (int dx
= -1; dx
<= 1; dx
++) {
62 //Skip diagonal neigbours
63 if (abs(dx
) == abs(dy
))
67 HASH_FIND(hh
, q
, &pnt(u
.x
+dx
, u
.y
+dy
), sizeof(struct point
), v
);
70 //Update dist if necessary
71 int alt
= dist
[u
.y
][u
.x
] + get_grid(v
->key
.x
, v
->key
.y
);
72 if (alt
< dist
[v
->key
.y
][v
->key
.x
]) {
73 dist
[v
->key
.y
][v
->key
.x
] = alt
;
74 //Reinsert with in correct position
75 HASH_DELETE(hh
, q
, v
);
76 HASH_ADD_INORDER(hh
, q
, key
, sizeof(struct point
), v
, qcmp
);
82 printf("%d\n", dist
[maxy
*MFAC
-1][maxx
*MFAC
-1]);