読者です 読者をやめる 読者になる 読者になる

「 今週のお題:道順は違っても結果は同じ」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 格子状のマス目 ( の一部 ) がある時に、上下左右で全てのマスを1度ずつ通る経路が何通りあるかを出力する
  • マス目の配置については、全てのマスを通る1つの経路が入力される。例えば、問題の例にあった次の図のようなマスの配置であれば、左側のような経路があるため、「上左下左」ということで“ULDL”という入力となる。( その他、「右右上左」の“RRUL”等もありうる )

https://codeiq.jp/sites/default/files/answer_ready/2880/q41.png

解説

入力文字列から、格子情報を構築し、スタート地点毎に経路数を加算していく再帰で解きました。
入力文字列を全て見ないと、有効なマスのある縦横のサイズが分からないため、文字列処理中に動的に拡張して格子情報を構築しています。
なお、端の処理を簡略化するため、上下左右の端にダミー領域を設けます。

経路探索では、既に通ったマスをビットマスクで管理します。
全部のマスを通るということは、通るマス数が一定になるので、再帰する際に残りのマス数を引数とし、最後のマスかどうかをチェックしています。

# 入力文字列から格子中の通ったマスを記録する関数
def makemap(s)
  m=[[true]]
  # 現在地
  x=y=0
  # 左右・上下のサイズ
  xlim=ylim=1
  # 有効なマス数 ( 重複したマスを辿らない前提 )
  n=s.size+1
  s.chars.each{|c|
    case c
    when ?U
      if y==0
        # 上端のため、全体を下にシフト
        m.unshift([false]*xlim)
        m[0][x]=true
        ylim+=1
      else
        m[y-=1][x]=true
      end  
    when ?D
      if (y+=1)==ylim
        # 下端のため、行を追加
        m.push([false]*xlim)
        m[y][x]=true
        ylim+=1
      else
        m[y][x]=true
      end
    when ?L
      if x==0
        # 左端のため、全体を右にシフト
        m.each{|r|r.unshift(false)}
        m[y][0]=true
        xlim+=1
      else
        m[y][x-=1]=true
      end
    when ?R
      if (x+=1)==xlim
        # 右端のため、列を追加
        m.each{|r|r.push(false)}
        m[y][x]=true
        xlim+=1
      else
        m[y][x]=true
      end
    end
  }
  # ダミー領域を上下左右の端に追加
  m.each{|r|
    r.unshift(false)
    r.push(false)
  }
  m.unshift([false]*(xlim+2))
  m.push([false]*(xlim+2))
  # 二次元リストおよび、ダミー領域を除く範囲のサイズ、有効なマスの数を返す
  [m,xlim,ylim,n]
end

def solve(m,xlim,ylim,n)
  # 経路の数
  a=0
  # 再帰的に経路を調べる関数
  f=->x,y,mask,r{
    # 有効なマスでなければ打ち切り
    return unless m[y][x]
    # 既に通ったマスなら打ち切り
    return if mask[y*xlim+x]!=0
    # 重複なく最後まで来たら経路数をカウント
    if (r-=1)==0
      a+=1
      return
    end
    # 現在地をマスクに登録して、上下左右に再帰
    mask|=1<<(y*xlim+x)
    f[x,y-1,mask,r]
    f[x,y+1,mask,r]
    f[x-1,y,mask,r]
    f[x+1,y,mask,r]
  }
  # それぞれの開始地点に対し、f を実行
  1.upto(ylim){|ys|
    1.upto(xlim){|xs|
      f[xs,ys,0,n]
    }
  }
  # 経路数を返す
  a
end

puts solve(*makemap(gets.chomp))

終わりに

本当のところを言うと、行き・帰りがちょうど逆になる経路半分だけ数えて倍にするとか、入力で与えられた経路の端を調べて、袋小路になっていたらそこが必ず端になるだろう、とか、効率を上げる方法は色々ありそうだったのですが…。まあ、これで間に合ってるからいっか、的な。