CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第101回「道順は違っても結果は同じ」

CodeIQというサイトで問題に挑戦した記録です。

問題文を要約すると下記の通り

• 正方形が縦横に敷き詰められたマス目を考える。
  このマス目を上下左右に一筆書きの要領で移動するとき、その経路を以下の要領で記録する。
• 上への移動は「U」、下への移動は「D」、右への移動は「R」、左への移動は「L」
• 上記の要領で移動した経路が標準入力から与えられる時、通ったマスと同じ形の図を異なった順序で移動する場合に一筆書きで移動できる経路が何通りあるかを解答する。

方針

再帰により探索し一筆書きができたパターンを数える。

入力文字の最大をMAX_Lとすると、縦横がMAX_L*2+1のサイズの二次元配列を2つ用意する。
（問題文の経路の読み込み用と訪問したマスの記録用）
標準入力より移動経路を読み込み配列に記録。 二次元配列の全てのマスより出発し、移動が可能なマスで未訪問である限り、4方向を探索する。
一筆書きが出来ればカウントする。

実装(Ruby)

では、

Sponsored Link