はじめに

アルゴリズムの勉強に、もっとプログラマ脳を鍛える数学パズルアルゴリズムが脳にしみ込む70問 を解いています。
経路問題がありましたので、Perl で実装してみました。

苦労した所

最小値のマスを取り出すため、2次元配列 cost[r][c] の値でソートし配列 que に格納された (r, c) 座標を返します。

ruby.rb

  que.sort_by!{|r, c| cost[r][c]}
  r, c = que.shift

javascript.js

  que.sort(function(a, b) {
    return cost[a[0]][a[1]] < cost[b[0]][b[1]];
  }
  var r, c;
  [r, c] = que.shift();

座標の受け渡しについて、後発の言語はスマートな感じがします。
特に、Ruby は、スッキリしていますね。

perl.pl

  @que = sort { $cost[$$_[0]][$$_[1]] } @que;
  my $in = shift @que;
  my ($r, $c) = ($$in[0], $$in[1]);

全ソース

q22_1.pl

use v5.18;
use warnings;

my @col = (8, 6, 8, 9, 3, 4, 1, 7, 6, 1);
my @row = (5, 1, 1, 9, 1, 6, 9, 0, 9, 6);

my (@board, @cost);
for my $r (0..@row-1) {
  for my $c (0..@col-1) {
    $board[$r][$c] = $row[$r] + $col[$c];
    $cost[$r][$c] = 2000;
  }
}

$cost[0][0] = $board[0][0];

my @que =[0, 0];
while (@que) {
#  @que = sort { $cost[$$b[0]][$$b[1]] <=> $cost[$$a[0]][$$a[1]] } @que; # 降順用
  @que = sort { $cost[$$_[0]][$$_[1]] } @que;
  my $in = shift @que;
  my ($r, $c) = ($$in[0], $$in[1]);
  if (0 <= $r - 1) {
    my ($x, $y) = ($r - 1, $c);
    if ($cost[$x][$y] > $cost[$r][$c] + $board[$x][$y]) {
      $cost[$x][$y] = $cost[$r][$c] + $board[$x][$y];
      push @que, [$x, $y];
    }
  }
  if (0 <= $c - 1) {
    my ($x, $y) = ($r, $c - 1);
    if ($cost[$x][$y] > $cost[$r][$c] + $board[$x][$y]) {
      $cost[$x][$y] = $cost[$r][$c] + $board[$x][$y];
      push @que, [$x, $y];
    }
  }
  if ($r + 1 < @row) {
    my ($x, $y) = ($r + 1, $c);
    if ($cost[$x][$y] > $cost[$r][$c] + $board[$x][$y]) {
      $cost[$x][$y] = $cost[$r][$c] + $board[$x][$y];
      push @que, [$x, $y];
    }
  }
  if ($c + 1 < @col) {
    my ($x, $y) = ($r, $c + 1);
    if ($cost[$x][$y] > $cost[$r][$c] + $board[$x][$y]) {
      $cost[$x][$y] = $cost[$r][$c] + $board[$x][$y];
      push @que, [$x, $y];
    }
  }
}
say $cost[@row - 1][@col - 1];

優先度付きキュー

Java では、java.util.PriorityQueue があります。
優先度付きキュー
計算量 O(1) + O(logN)
(上記 sort は O(N) + O(N) )

Ruby で実装されている方もいらっしゃいます。
競プロの為にRubyでヒープ(優先度付きキュー)作った(ABC128E)
Ruby で Priority Queue を実装してみたい

まとめ

ダイクストラ法について少しだけ知見を得た

参照したサイト
Perlのdeleteでひっかかった話

追記

add.pl

  @que = sort { $cost[$$_[0]][$$_[1]] } @que;
  my ($r, $c) = map{$$_[0], $$_[1]} shift @que;

perl でも2行で記述できましたが、ruby のスッキリ感には程遠い感じです。