X-Git-Url: https://www.fi.muni.cz/~kas/git//home/kas/public_html/git/?a=blobdiff_plain;f=29.pl;fp=29.pl;h=d4a24412a94eb8e2fa98cb03eec1c6291836b37f;hb=0febc3a8a728adf5c84e9049f443b85414bfcb79;hp=0000000000000000000000000000000000000000;hpb=34f4f573f50f907f680f7d463c792f4f1a6e53d8;p=aoc2021.git

diff --git a/29.pl b/29.pl
new file mode 100755
index 0000000..d4a2441
--- /dev/null
+++ b/29.pl
@@ -0,0 +1,34 @@
+#!/usr/bin/perl -w
+
+use v5.16;
+use Data::Dumper;
+
+$; = ',';
+my @m;
+my ($maxx, $maxy) = (0, 0);
+while (<>) {
+	chomp;
+	push @m, [ split // ];
+	$maxx = length;
+	$maxy++;
+}
+
+my %cost = ("0,0" => 0);
+my @todo = ([0, 0]);
+
+while (my $p = shift @todo) {
+	my ($sx, $sy) = @$p;
+	for my $d ([ 0, 1], [0, -1], [1, 0], [-1, 0]) {
+		my $dx = $sx + $d->[0];
+		my $dy = $sy + $d->[1];
+		next if $dx < 0 || $dx >= $maxx || $dy < 0 || $dy >= $maxy;
+		if (!defined $cost{$dx,$dy}
+			|| $cost{$dx,$dy} > $cost{$sx,$sy} + $m[$dy][$dx]) {
+			$cost{$dx,$dy} = $cost{$sx,$sy} + $m[$dy][$dx];
+			push @todo, [$dx,$dy];
+		}
+	}
+}
+
+say $cost{$maxx-1,$maxy-1};
+