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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
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);
}
|
