私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「極めよプログラミング道！【実力判定：Sランク】」（CodeIQ）を参照してください。
【問題】
0から9の整数を、縦横それぞれN個並べた四角形があります。
左上から右下に、右あるいは下へと移動しながら、数を足していきます。
複数ある経路のうち、最小合計値となる経路をたどった場合の、合計値を答えてください。
ただし、Nは、2≦N≦20 の範囲の整数とします。
例
567
133
502
上記の場合の全経路と合計値。
route: 56732, sum: 23
route: 56332, sum: 19
route: 56302, sum: 16
route: 51332, sum: 14
route: 51302, sum: 11
route: 51502, sum: 13
上記の場合の、最小合計値となる経路の図示。
567
133
502
最小合計値は「11」。
【入力】
標準入力から、複数行のデータが与えられます。縦横同じ文字数で、1つの正方形が作られます。
【出力】
最小合計値となる経路をたどった場合の合計値を、標準出力に出力します。
567
133
502
11
Rubyで解答しています。
#!/usr/bin/ruby
def solve(map)
y = map.size
x = map[0].size
ret = Array.new(y){Array.new(x, -1)}
ret[0][0] = map[0][0]
1.upto(x-1){|n|
n.downto(0){|i|
j = n - i
s1 = -1
s1 = ret[j-1][i] + map[j][i] if j-1 >= 0
s2 = -1
s2 = ret[j][i-1] + map[j][i] if i-1 >= 0
if s1 == -1 then ret[j][i] = s2
elsif s2 == -1 then ret[j][i] = s1
else ret[j][i] = (s1 < s2 ? s1 : s2)
end
}
}
1.upto(y-1){|m|
(x-1).downto(m){|i|
j = m + (x-1) - i
s1 = -1
s1 = ret[j-1][i] + map[j][i] if j-1 >= 0
s2 = -1
s2 = ret[j][i-1] + map[j][i] if i-1 >= 0
if s1 == -1 then ret[j][i] = s2
elsif s2 == -1 then ret[j][i] = s1
else ret[j][i] = (s1 < s2 ? s1 : s2)
end
}
}
return ret[y-1][x-1]
end
# main
map = []
while line = gets
line.strip!
next if line.empty?
l = line.split("").map{|a| a.to_i}
map << l
end
p solve(map)
★★★★の問題としては簡単です。
が、2≦N≦20は嘘です。騙されました。
| 5 | - | - |
| - | - | - |
| - | - | - |
| 5 | - | - |
| - | - | - |
| - | - | - |
| 5 | 11 | - |
| 6 | - | - |
| - | - | - |
| 5 | 11 | 18 |
| 6 | 9 | - |
| 11 | - | - |
| 5 | 11 | 18 |
| 6 | 9 | 12 |
| 11 | 9 | - |
| 5 | 11 | 18 |
| 6 | 9 | 12 |
| 11 | 9 | 11 |
入力値を取得し数値に変換して二次元配列mapに保持します。
solve()に渡して結果を印字します。
考え方の通りに実装しています。
x,yはマップの幅と高さです（別に区別しなくてもこの問題には関係ありません）。
retは結果を保持するための二次元配列で、mapと同サイズで作成しておきます。入力値が0以上なので初期値は-1にしています。
8行目で左上の値をretの最初の値としてセットしています。
10〜25行目のループは左上から2ライン目から右上から左下の角を結ぶもっとも長いラインまでの計算を行なっています。
12行目で何列目かを基準としてi列目のj行目を計算しています。11行目のループの開始が計算している斜めのラインの、0行目のもっとも右側の列なのでそこから1列左に移動するごとに1行ずつ下に移動することで計算する場所を特定しています。
14〜15行目で上側のretの値、17〜18行目で左側のretの値とmapの値を足しています。領域外の場合は-1になります。
20〜23行目で値をretの当該位置に設定しています。上側か左側が領域外の場合はs1かs2が-1なのでその場合は値がある方を自動的に設定し、そうでなければ値の小さい方を設定します。
27〜42行目のループは右上から左下の角を結ぶもっとも長いラインの次のラインから右下までを10〜25行目までと同じように計算しています。
位置の計算だけの違いなので説明は省略します。
最終的にretの最後の要素に答えが入っているのでそれを返却します。
ソートして、要素数が奇数なら中央の値、要素数が偶数なら中央2個の値の平均値の小数点以下第二位を四捨五入して返します。
問題を読んだ瞬間、ダイクストラ法で余裕でできるじゃねーか、簡単すぎるな、と思いました。問題文だと2≦N≦20しかありませんし。
で、最初普通にqueueを使ったダイクストラ法で実装しました。そうしたら最大のテストケースが1000*1000じゃないですか。1秒では終わりませんよ、そりゃ（3秒あまりだったのでCかC++で書き直せば終わりますけど）。
酷いだまし討ちだ、ということで回答のコードになりました。
本質的に違いはありませんが、ダイクストラ法に比べてqueueへの追加、削除が発生しないのでこのコードの方が高速です。