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(self.v, other.v);
    }

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