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(@bitCast(u32, self), @bitCast(u32, other));
    }

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