Help us understand the problem. What is going on with this article?

オフラインリアルタイムどう書く第四回の参考問題

More than 5 years have passed since last update.

オフラインでリアルタイムに「どう書く」をやるイベント。
またやります
http://atnd.org/events/32191
で。例によって参考問題。
難易度と分量はこれを目安にと言いたいところだけれども、たぶんこれは難しすぎる。
こんなに難しい問題は出しませんよ、という意味で参考に。

フカシギの数え方( http://www.youtube.com/watch?v=Q4gTV4r0zRs )が余りにも素晴らしかったので、そこから

フカシギの通行止め

4✕4 のマス目の辺を通っての左上から右下に行く方法は何通りあるか計算する。
※ ビデオに合わせて 4✕4 と書いたが、縦に5本 横にも5本の道があり、頂点数は 25個である。
ただし

  • 同じ頂点を二度通ってはいけない。
  • ところどころ行き止まりがある。
  • ビデオを見るとわかるが、行き止まりなしで 8512通り。
  • 不正入力には対処しなくてよい。

行き止まりを表現するために、頂点に a〜y の名前を順につける。
入力文字列が "fg gh" なら、行き止まりは二箇所。fとgの間とgとhの間。

入力と出力の例

以下、"入力" -> 出力 # コメント の形式で例を示す

"" -> 8512 #そのまま。これが最大値。
"af" -> 4256 #対称性より半分になる
"xy" -> 4256 #対称性より半分になる
"pq qr rs st di in ns sx" -> 184 #3x3マスと同値
"af pq qr rs st di in ns sx" -> 92 #3x3マスのパターンの半分
"bg ch di ij no st" -> 185 #3x3マスのパターン +1
"bc af ch di no kp mr ns ot pu rs" -> 16 #4x2x2
"ab af" -> 0 #入口を塞いだ
"ty xy" -> 0 #出口を塞いだ
"bg ch ej gh lm lq mr ot rs sx" -> 11 #2x4+3
"ty ch hi mn kp mr rs sx" -> 18 #6*3
"xy ch hi mn kp mr rs sx" -> 32 #4*8
"ch hi mn kp mr rs sx" -> 50 #6*3+4*8
"ab cd uv wx" -> 621
"gh mn st lq qr" -> 685
"fg gl lm mr rs" -> 171

※ 解答例をコメント欄に(ソースではなく)リンクの形で書いてくださるとありがたいです。
※ そのうち ruby か groovy で解答例を投稿するつもり。

Nabetani
横浜へなちょこプログラミング勉強会をやっていました。 / CodeIQ の出題者でした。 / 日経 WinPC に連載を持っていました(名義が違うけど) / Yokohama rb に半分ぐらい参加しています。 / twitter : http://twitter.com/Nabetani
https://nabetani.hatenadiary.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away