私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「魔法使いの梯子(はしご)」（CodeIQ）を参照してください。
【概要】
5×5 のマス目があります。あなたはそこを歩きます。
マス目にある 0〜9 の数は、マス目の高さを表しています。
スタート地点は、上辺の中央（右図では「3」の位置）です。
そこからマス目を上下左右に歩いていきます。
1 2 3 4 5 1 8 4 0 5 4 1 0 1 5 5 2 1 5 2 6 7 9 5 2
移動できるのは、基本的に
自分のいるマスと同じ高さのマス
自分のいるマスよりひとつ低い（マス目の数字がひとつ小さい）マス
自分のいるマスよりひとつ高い（マス目の数字がひとつ大きい）マス
のいずれかです。
ただし。
あなたは魔法使いの梯子をひとつだけ持っています。
魔法使いの梯子を使うと、自分のいるマスのより2〜3段高い、または2〜3段低いマスまで移動できます。
魔法使いの梯子は一度使うと消えてしまいます。
到達可能なマスを「*」で表した地図を作ってください。
【入出力】
入力は
12345/18405/41015/52152/67952
のようになっています。
上から順にマスの高さが書かれています。
行区切りはスラッシュです。
出力するのは、入力と同じ形式の地図で、到達可能なマスを「*」で置換したものです。
12345/18405/41015/52152/67952
に対応する出力は
*****/*8*0*/*101*/*215*/**95*
になります。
【例】
入力 出力 図 12345/18405/41015/52152/67952 *****/*8*0*/*101*/*215*/**95*
1 2 3 4 5 1 8 4 0 5 4 1 0 1 5 5 2 1 5 2 6 7 9 5 2 11911/22822/33933/44944/55555 11*11/22*22/33*33/44*44/55555
1 1 9 1 1 2 2 8 2 2 3 3 9 3 3 4 4 9 4 4 5 5 5 5 5 00000/11311/22622/33933/44944 *****/*****/**6**/**9**/**9**
0 0 0 0 0 1 1 3 1 1 2 2 6 2 2 3 3 9 3 3 4 4 9 4 4
【補足】
不正な入力に対処する必要はありません。
魔法使いの梯子は使わなくても構いません。
Rubyで解答しています。
#!/usr/bin/ruby
$Map = nil
$Memo = Array.new(5){Array.new(5, 0)}
def move(row, col, rad)
dir = [[-1,0], [0,+1], [+1,0], [0,-1]]
$Memo[row][col] = rad + 1
for d in dir
nr = row + d[0]
nc = col + d[1]
next if (nr < 0) || (nc < 0) || (5 <= nr) || (5 <= nc)
next if $Memo[nr][nc] >= rad + 1
hsub = ($Map[row][col] - $Map[nr][nc]).abs
if hsub <= 1 then
move(nr, nc, rad)
elsif (hsub <= 3) && (rad > 0) then
move(nr, nc, rad-1)
end
end
return
end
def getResult()
ret = []
for r in 0...5
l = ""
for c in 0...5
if $Memo[r][c] > 0 then l += '*'
else l += $Map[r][c].to_s
end
end
ret << l
end
return ret.join('/')
end
def solve()
move(0, 2, 1)
return getResult()
end
# main
while line = gets
line.strip!
next if line.empty?
$Map = line.split('/').map{|row| row.split('').map{|a| a.to_i}}
end
puts solve()
それほど難しくは無いと思います。
ポイントは魔法使いの梯子をどう扱うかでしょうか。
入力値をパースして数値の二次元配列にし、$Mapに保持します。
$Memoは到達地点の管理用の二次元配列で、未到達の場所を0、梯子使用済みで到達した場所を1、梯子未使用で到達した場所を2とします。
solve()を呼び、問題を解いて結果を印字します。
move()で$Mapを探索します。
getResult()は$Memoを結果文字列にするので、その返却値を返します。
引数rowは現在地点の行番号、colは列番号です。
radは残り梯子数です。
dirは移動方向のリストです。
まず、現在地点に到達した印を$Memoに記録します。
梯子を使わずに到達した場合は2、梯子を使って到達した場合は1なのでrad+1を$Memoの当該座標に記録します。
全ての方向に対して移動を試します。
範囲外なら無視します。
$Memoの次の移動先の値がrad+1以上の場合、つまり梯子未使用で到達した場所に再度到達した場合は無視します。$Memoの値が1でrad=1（梯子未使用）で到達した場合は無視しないので、この処理で梯子未使用が梯子使用済みよりも優先されることになります。
次に現在地点と異動先の高さを比較します。
高さの差が1以下なら移動できるのでmove()を再帰呼び出しします。
高さが3以下で梯子に残りがあるならやはり移動可能なのでmove()を再帰呼び出しします。
再帰呼び出しされなくなった時点で$Memoには到達可能場所が1か2、到達できなかった場所が0で記録されることになります。
$Memoを見て1か2なら*、0なら$Mapの値にし、1行ごとに'/'で連結して返します。
分かりやすい問題だったと思います。
試していませんが、私のコードは梯子数が2以上でもうまく問題を解けるはずです。