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

糸電話式のアレ

プログラミングのこと。毎日のこと。書いています。

今流行のお題を出してみた

プログラミング

*いろんな言語で実装してみてください。実装できたら、この記事へトラックバックをしていただけると嬉しいです。

問題

一方通行を許可した迷路を作成する。
10×10=100マスに合同な正方形のセルを並べて、そのセルの間をドアで繋いで経路を作成する。
ドアには鍵が掛かっていることがあり、一方通行とすることができる。
ドアは両側から開くドアとすることもできる。
スタート地点となるセルとゴール地点となるセルは任意に設定できる(=どのセルをスタート地点にしても全ての経路を辿れること)。


以下に、上記説明と重複する部分があるが、条件と実装の仕様をまとめる。

条件

  1. セルは正方形であり、全てのセルの面積は同じである。
  2. セルは 10 × 10の行列をなす100マスで構成されている。
  3. セルは、隣り合うセルに移動するためのルートをひとつ以上持っている。(ひとつのセルから出られなくなることはない)
  4. あるセルから別のセルへの移動は、隣り合う関係のセル同士でのみ可能である。(セルを飛ばして移動したりしない)
  5. 隣り合う関係のセルAとセルBで、セルAからセルBへの移動するルートがあるとき、セルBからセルAに移動できることは保証しない。(一方からのみ移動できる場合がある)
  6. セルから、隣り合うひとつのセルへ移動できる確率は、全てのセル間の移動できる確率を平均して60%以内である。
  7. 全てのセルは、そのセルを出発点として全てのセルへ移動できる。(どこから出発してもどこへでも行ける)
  8. 経路はランダムで決定する。ランダム性については実装者にて判断してよい。

実装の仕様

  • 条件を満たす迷路を生成する機能を作成する。
  • 生成した迷路のひとつのセルは、次のXML要素で表現する。
    • <cell doors="East:true,West:false,South:true,North:false" position="1,1"></cell>
    • cell:固定
    • doors:コロン区切りのタプルで移動可能方向をtrueとするカンマ区切りのマップ表現(falseとなる場合のキーは必須ではない)
    • position:1,1-10,10でカラムの座標を表現する。左右上下の値増加の方向は特に問わない。
  • 迷路全体は、上記の要素が100個並んだ形式で表現する。
  • XML表現の迷路が、条件に合致しているかを判定する機能を作成する。
更新(2011/04/02)

確率が低すぎて難しいことがわかったので40%→60%にします。