1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
const FixedBufferAllocator = std.heap.FixedBufferAllocator;
const Order = std.math.Order;
const PQ = std.PriorityQueue;
const input = @embedFile("input");
const order = std.math.order;
const print = std.debug.print;
const std = @import("std");
const Risk = packed struct {
x: u9,
y: u9,
v: u22,
pub fn lt(self: Risk, other: Risk) Order {
return order(@bitCast(u40, self), @bitCast(u40, other));
}
pub fn move(self: Risk, queue: *PQ(Risk), dx: i10, dy: i10) !void {
switch (self.x + dx) {
0...499 => |x| switch (self.y + dy) {
0...499 => |y| try queue.add(.{
.v = self.v + @intCast(u22,
input[@intCast(usize, @rem(x, 100))
+ @intCast(usize, @rem(y, 100)) * 101] - '1'
+ @divTrunc(x, 100) + @divTrunc(y, 100)) % 9 + 1,
.x = @intCast(u9, x), .y = @intCast(u9, y),
}),
else => {},
},
else => {},
}
}
};
pub fn main() !void {
var visited = [_][500]bool{ [_]bool{ false } ** 500 } ** 500;
var buffer: [0xbeef]u8 = undefined;
var fba = FixedBufferAllocator.init(buffer[0..]);
var queue = PQ(Risk).init(&fba.allocator, Risk.lt);
try queue.add(.{ .x = 0, .y = 0, .v = 0 });
const result = while (queue.count() > 0) {
const best = queue.remove();
if (best.x == 499 and best.y == 499)
break best.v;
if (visited[best.x][best.y])
continue
else
visited[best.x][best.y] = true;
try best.move(&queue, 1, 0);
try best.move(&queue, 0, 1);
try best.move(&queue, -1, 0);
try best.move(&queue, 0, -1);
} else unreachable;
print("{}\n", .{ result });
}
|
