DouKaku? 5277 yuin: たまには一番乗り狙いで。シンプル...(必ず解ける迷路)

Comment detail

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

シンプルに穴掘り法を使いました。また速度重視ということで手続き型スタイルな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?

Comment detail

Index

Feed

Other

Link

Pathtraq