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
|
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: u7,
y: u7,
v: u18,
pub fn lt(self: Risk, other: Risk) Order {
return order(self.v, other.v);
}
pub fn move(self: Risk, queue: *PQ(Risk), dx: i8, dy: i8) !void {
switch (self.x + dx) {
0...99 => |x| switch (self.y + dy) {
0...99 => |y| try queue.add(.{
.x = @intCast(u7, x), .y = @intCast(u7, y),
.v = self.v + input[@intCast(usize, x)
+ @intCast(usize, y) * 101] - '0',
}),
else => {},
},
else => {},
}
}
};
pub fn main() !void {
var visited = [_][100]bool{ [_]bool{ false } ** 100 } ** 100;
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 == 99 and best.y == 99)
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 });
}
|
