必ず解ける迷路 in Scala DouKaku?

以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。

1. 格子状の迷路であること。
2. 経路の幅は均等であること。
3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。
   ループも認めません。
4. 出力の度にランダムな迷路であること。
   ランダムシードが同じ時に同じ迷路になってしまうのはよいです。

たとえば、n=4, m=5の迷路の出力は以下のようになります。

　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■　　　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　■　　　■　■
―■■■■■■■■■

こう言うのは、×の部分が3のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■×■　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■■■　■
４■　■×××■　■
―■　■×■■■　■
５■　■×××■　■
―■■■■■■■■■

このようなループも2のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　　　■　■
―■■■　■　■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　　　　　■　■
―■■■■■■■■■

できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。


難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を
どうやって作るのかを考えると答えが見えてくると思います。
ソースコードはJavaで150行程度になりました。

たまには一番乗り狙いで。

シンプルに穴掘り法を使いました。また速度重視ということで手続き型スタイルなScalaになっています。

CPU : Athlon64 3000+
OS : XP
MEM : 1G

な環境で

出力なし: 45～50秒
出力をファイルへリダイレクト : 2分程度

でした。

import java.util.Random
import java.lang.Integer.parseInt
import scala.collection.mutable.{HashMap, Stack}
import scala.util.Sorting.stableSort

object main{
  def main(args: Array[String]) = {
    mazeGenerate(parseInt(args(0)),parseInt(args(1)))
  }

  type Coord = (int, int)
  final val BLANK = '■'
  final val FILL = '□'

  def mazeGenerate(_n:int, _m:int) = {
    val n = _n*2+1
    val m = _m*2+1
    val map    = new HashMap[Coord, Char]
    val stack  = new Stack[Coord]
    val ramdom = new Random
    val range = Array(0,1,2,3)

    def badCoord_?(c:Coord) = 
        map.getOrElse(c, BLANK) == FILL || c._1 > n-2 || c._1 < 1 || c._2 > m-2 || c._2 < 1
    
    stack += (1,1)
    map(stack.top) = FILL
    var break=false; while(!break) {
      var c = stack.top
      var siblings = Array((c._1, c._2-2), (c._1+2, c._2), (c._1-2, c._2), (c._1, c._2+2))
      if(siblings.forall(badCoord_?(_))){
        stack.pop
        if(stack.isEmpty) { break=true }
      }else {
        var candies = stableSort[int,int](range, { x=>ramdom.nextInt(4) })
        var break2=false;var i= -1; while({i = i+1; !break2&&i<4}) {
          var sibling = siblings(candies(i))
          if(!badCoord_?(sibling)) {
            var (x,y) = (sibling._1-c._1, sibling._2-c._2)
            stack += sibling
            if(x != 0) {
              map((c._1+x/2, c._2)) = FILL
            }else {
              map((c._1, c._2+y/2)) = FILL
            }
            map(sibling) = FILL
            break2 = true
          }
        }
      }
    }

    for(i <- (0 until m); j <- (0 until n)) {
      print(map.getOrElse((j,i), BLANK))
      if(j == n-1){ println("") }
    }
  }
}

ふつうに配列を使った版。

CPU : Athlon64 3000+
OS : XP
MEM : 1G

な環境で1024 1024が

出力をファイルへリダイレクト : Elapsed Time: 0:00:10.062

でした。

import java.util.Random
import java.lang.Integer.parseInt
import scala.collection.mutable.{HashMap, Stack}
import scala.util.Sorting.stableSort

object main{
  def main(args: Array[String]) = {
    mazeGenerate(parseInt(args(0)),parseInt(args(1)))
  }

  type Coord = (int, int)
  final val BLANK:char = '■'
  final val FILL:char = '□'

  def mazeGenerate(_n:int, _m:int) = {
    val n = _n*2+1
    val m = _m*2+1
    val map:Array[Array[char]] = Array.make(m, 0).map(x=>Array.make(n, BLANK))
    val stack  = new Stack[Coord]
    val ramdom = new Random
    val range = Array(0,1,2,3)

    def badCoord_?(c:Coord) = 
      c._1 > n-2 || c._1 < 1 || c._2 > m-2 || c._2 < 1 || map(c._2)(c._1) == FILL 
    
    stack += (1,1)
    map(1)(1) = FILL
    var break=false; while(!break) {
      var c = stack.top
      var siblings = Array((c._1, c._2-2), (c._1+2, c._2), (c._1-2, c._2), (c._1, c._2+2))
      if(siblings.forall(badCoord_?(_))){
        stack.pop
        if(stack.isEmpty) { break=true }
      }else {
        var candies = stableSort[int,int](range, { x=>ramdom.nextInt(4) })
        var break2=false;var i= -1; while({i = i+1; !break2&&i<4}) {
          var sibling = siblings(candies(i))
          if(!badCoord_?(sibling)) {
            var (x,y) = (sibling._1-c._1, sibling._2-c._2)
            stack += sibling
            map(c._2+y/2)(c._1+x/2) = FILL
            map(sibling._2)(sibling._1) = FILL
            break2 = true
          }
        }
      }
    }

    map.map(_.mkString("")).foreach(println)
  }
}

DouKaku?

必ず解ける迷路

Posted feedbacks - Scala

Index

Feed

Other

Link

Pathtraq