「MENMA」を探そう【解説】

• 本稿はCodeIQで出題された 第1回プロコン：【猿】偏食の猿の好き嫌いを見極めよう という問題の解答例と簡単な解説です。

• 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ！」とか、「こう書いた方がわかりやすいよ！」とか、「他の言語で書いてみたよ！」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

「MENMA」を探そう【解説】

◆解説

これは検索文字列"MENMA"の文字数を深さの最大とした深さ優先探索を素直に実装するだけの問題です。テストケースは大きくありませんので、特別な工夫を行う必要はありません。落ち着いてコーディングしましょう。

◆解答例

#!ruby

$w = "MENMA"
$v = STDIN.readlines.map{|s|s.strip.split''}

def dfs(d, cx, cy, ox, oy)
  
  return $w[d] == $v[cx][cy] if d+1==$w.size
  
  return false if $w[d] != $v[cx][cy]
  
  [ [-1,0], [1,0], [0,-1], [0,1] ].each{|u|
    nx, ny = [cx,cy].zip(u).map{|t|t.inject(&:+)}
    next if [nx,ny] == [ox,oy]
    next if nx<0 || ny<0 || nx>=$v.size || ny>=$v.size
    
    return true if dfs(d+1, nx, ny, cx, cy)
  }
  
  return false
end

n = $v.size
n.times{|i|
  n.times{|j|
    if dfs(0, i, j, i, j)
      puts"yes"
      exit
    end
  }
}

puts"no"