Eng: Trying not to lose my working knowledge of Perl I decided to write this problem using it. The more general solution is where you can move up, down, left and right in which case you must use Dijkstra's algorithm using a matrix as the data structure. However for this particular problem you can only move down or right which makes it a lot easier. The algorithm just traverses the matrix in diagonal strips and adds its upper and left cell:
use strict;
use warnings;
$| = 1; #turn autoflush on
use Text::CSV;
my @data; # 2D array for CSV data
my $file = 'matrix.txt';
my $csv = Text::CSV->new;
open my $fh, '<', $file or die "Could not open $file: $!";
while( my $row = $csv->getline( $fh ) ) {
print join(", ", @$row) ."\n";
#shift @$row; # throw away first value
push @data, $row;
}
my $w = scalar @{$data[0]};
for (my $slice = 0; $slice < 2 * $w - 1; ++$slice) {
my $z = $slice < $w ? 0 : $slice - $w + 1;
for (my $j = $z; $j <= $slice - $z; ++$j) {
my $x = $j;
my $y = $slice - $j;
my $val = $data[$x][$y];
if($x - 1 <= 0 && $y - 1 >= 0){
$val += ($data[$x-1][$y] > $data[$x][$y-1])?$data[$x][$y-1]:$data[$x-1][$y];
} else {
if($x - 1 >= 0){
$val += $data[$x-1][$y];
}
if($y - 1 >= 0){
$val += $data[$x][$y-1];
}
}
print "x: $x, y: $y, data: $data[$x][$y], val: $val\n";
$data[$x][$y] = $val;
}
}
for (my $i = 0; $i < $w; $i++){
for(my $j = 0; $j < $w; $j++){
print $data[$i][$j] ." ";
}
print "\n";
}
print "res: " . $data[$w-1][$w-1];
No hay comentarios:
Publicar un comentario