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 }); }