const std = @import("std");
const print = std.debug.print;
const assert = std.debug.assert;
const ArrayList = std.ArrayList;
const HashMap = std.HashMap;
const mem = std.mem;
const math = std.math;

const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();

const move = [_][2]i64{
    [_]i64{ -1, 0 },
    [_]i64{ 0, 1 },
    [_]i64{ 1, 0 },
    [_]i64{ 0, -1 },
};

const Point = struct {
    i: usize,
    j: usize,
    best: [4]u64,

    pub fn Cmp(_: void, lhs: Point, rhs: Point) math.Order {
        return std.math.order(mem.min(u64, &lhs.best), mem.min(u64, &rhs.best));
    }
};

const inf: u64 = math.maxInt(u32);
const MAXSIZE = 200;

fn evaluate(grid: []const []const u8, comptime min_dist: u64, comptime max_dist: u64) !u64 {
    var dp = [_][MAXSIZE][4]u64{[_][4]u64{[_]u64{inf} ** 4} ** MAXSIZE} ** MAXSIZE;
    const w = grid[0].len;
    const h = grid.len;
    var pq = std.PriorityQueue(Point, void, Point.Cmp).init(allocator, {});

    dp[0][0] = [_]u64{0} ** 4;

    try pq.add(Point{
        .i = 0,
        .j = 0,
        .best = dp[0][0],
    });

    while (pq.removeOrNull()) |curr| {
        for (move, 0..) |m, dirTo| {
            const dirFrom = dirTo ^ 0b10;
            const dpbest = res: {
                var best: u64 = inf;

                for (0..4) |dir| {
                    if (dir != dirFrom and dir != dirTo) {
                        best = @min(best, dp[curr.i][curr.j][dir]);
                    }
                }

                break :res best;
            };

            var s: u64 = 0;
            for (1..max_dist + 1) |dist| {
                const ni: u64 = @bitCast(@as(i64, @bitCast(curr.i)) + m[0] * @as(i64, @bitCast(dist)));
                const nj: u64 = @bitCast(@as(i64, @bitCast(curr.j)) + m[1] * @as(i64, @bitCast(dist)));

                if (ni >= h or nj >= w) {
                    break;
                }

                s += grid[ni][nj] - '0';

                if (dist < min_dist) {
                    continue;
                }

                if (dp[ni][nj][dirFrom] > dpbest + s) {
                    dp[ni][nj][dirFrom] = dpbest + s;
                    try pq.add(Point{
                        .i = ni,
                        .j = nj,
                        .best = dp[ni][nj],
                    });
                }
            }
        }
    }
    return mem.min(u64, &dp[h - 1][w - 1]);
}

pub fn solve(grid: []const []const u8) !void {
    const part1 = try evaluate(grid, 1, 3);
    print("{d}\n", .{part1});

    const part2 = try evaluate(grid, 4, 10);
    print("{d}\n", .{part2});
}

pub fn main() !void {
    var splitLines = mem.splitScalar(u8, fin, '\n');
    var grid = ArrayList([]const u8).init(allocator);

    while (splitLines.next()) |line| {
        try grid.append(line);
    }

    try solve(grid.items);
}