68 lines
2.4 KiB
C#
68 lines
2.4 KiB
C#
// #define Day15
|
|
#if Day15
|
|
using System.Collections.Immutable;
|
|
using System.Diagnostics;
|
|
using AoC2021;
|
|
|
|
var lines = File.ReadAllLines("day15/input");
|
|
var cave = new int[lines.Length, lines[0].Length];
|
|
lines.ForEachIndex((l, row) => l.ForEachIndex((c, col) => cave[row, col] = int.Parse(c.ToString())));
|
|
|
|
Console.WriteLine(Check(cave));
|
|
|
|
int rowLength = cave.GetLength(0);
|
|
int colLength = cave.GetLength(1);
|
|
var largerCave = new int[lines.Length * 5, lines[0].Length * 5];
|
|
for (int timeRow = 0; timeRow < 5; timeRow++) {
|
|
for (int timesCol = 0; timesCol < 5; timesCol++) {
|
|
for (int row = 0; row < rowLength; row++) {
|
|
for (int col = 0; col < colLength; col++) {
|
|
largerCave[rowLength * timeRow + row, colLength * timesCol + col] = ((cave[row, col] + timeRow + timesCol - 1) % 9) + 1;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
Console.WriteLine(Check(largerCave));
|
|
|
|
long Check(int[,] caveToCheck) {
|
|
var pos = new Point(0, 0);
|
|
var end = new Point(caveToCheck.GetLength(0) - 1, caveToCheck.GetLength(1) - 1);
|
|
var visitedLowest = new Dictionary<Point, long>() { { pos, 0 } };
|
|
var minPaths = new PriorityQueue<PointWithVisited, long>();
|
|
minPaths.Enqueue(new PointWithVisited(pos, ImmutableHashSet.Create<Point>()), 0);
|
|
|
|
while (true) {
|
|
minPaths.TryDequeue(out PointWithVisited cur, out long min);
|
|
if (cur.point.Equals(end)) {
|
|
return min;
|
|
}
|
|
|
|
var adjacent = GetAdjacent(cur.point, cur.visited, caveToCheck);
|
|
var nextVisited = cur.visited.Add(cur.point);
|
|
foreach (var a in adjacent) {
|
|
var riskLevel = min + caveToCheck[a.row, a.col];
|
|
if (visitedLowest.ContainsKey(a) && visitedLowest[a] <= riskLevel) {
|
|
continue;
|
|
}
|
|
visitedLowest[a] = riskLevel;
|
|
minPaths.Enqueue(new PointWithVisited(a, nextVisited), riskLevel);
|
|
}
|
|
}
|
|
}
|
|
|
|
List<Point> GetAdjacent(Point cur, ImmutableHashSet<Point> visited, int[,] caveToCheck) {
|
|
return new List<Point>() {
|
|
new Point(cur.row + 1, cur.col),
|
|
new Point(cur.row - 1, cur.col),
|
|
new Point(cur.row, cur.col + 1),
|
|
new Point(cur.row, cur.col - 1),
|
|
}.Where(p => p.row >= 0 && p.row < caveToCheck.GetLength(0) && p.col >= 0 && p.col < caveToCheck.GetLength(1))
|
|
.Where(p => !visited.Contains(p))
|
|
.ToList();
|
|
}
|
|
|
|
record PointWithVisited(Point point, ImmutableHashSet<Point> visited);
|
|
|
|
record Point(int row, int col);
|
|
#endif |