一方通行迷路の問題の回答

labyrinth.groovy

// aya_eiyaさんのお題 http://d.hatena.ne.jp/aya_eiya/20110329/1301406161 を
// deve68さんの方式に従って解いてみた回答 http://d.hatena.ne.jp/deve68/20110410/1302464249
// 判定機能は未実装

final def MAXCOL = 10
final def MAXROW = 10
assert (MAXCOL == MAXROW) && (MAXCOL >= 2)

// ノードクラス
class Node {
  int col
  int row
  boolean isVisited = false
  boolean east = false
  boolean west = false
  boolean south = false
  boolean north = false
  Node(c, r) {
    col = c
    row = r
  }
  String toXML() { "East:${east},West:${west},South:${south},North:${north}" }
  String toString() { "R${col}${row}" }
}

// 全てのノード(部屋)を作成する
def nodes = []
[0..<MAXCOL, 0..<MAXROW].combinations().each { col, row ->
  if( !nodes[col] ) nodes[col] = new ArrayList()
  nodes[col] << new Node(col,row)
}

// fromNodeに隣接する全ノードを返却する
def getAdjacentNodes = { fromNode ->
  def tmp = []
  if( fromNode.row >  0 )         tmp << nodes[fromNode.col][fromNode.row-1]
  if( fromNode.row < (MAXROW-1) ) tmp << nodes[fromNode.col][fromNode.row+1]
  if( fromNode.col >  0 )         tmp << nodes[fromNode.col-1][fromNode.row]
  if( fromNode.col < (MAXCOL-1) ) tmp << nodes[fromNode.col+1][fromNode.row]
  return tmp
}

// fromNodeから出る全エッジ(= [fromNode, fromNodeに隣接するノード]のペア)を返却する
def getNextEdges = { fromNode ->
  getAdjacentNodes(fromNode).collect { toNode -> [ fromNode, toNode ] }
}

// プリム法を用いて全域木を作成する
// (全てのエッジの重みが同じであると仮定して次のエッジをランダムに選択)
def createPrimSpanningTree = { current ->
  def resultEdges = []
  def nextEdges = []
  [0..<MAXCOL, 0..<MAXROW].combinations().each {
    def tmp
    current.isVisited = true
    // トラバース可能なエッジを追加する
    nextEdges.addAll(getNextEdges(current))
    // 終端ノードがトラバース済みであるエッジを削除する
    if( nextEdges ) {
       nextEdges.removeAll { it[1].isVisited }
    }
    if( nextEdges ) {
      tmp = nextEdges.remove((int)Math.random() * nextEdges.size())
      resultEdges << tmp  // ランダムに選んだエッジを木に追加する
      current = tmp[1]    // エッジの終端を次の起点にする
    }
  }

  // ノードのトラバース情報をリセットする
  [0..<MAXCOL, 0..<MAXROW].combinations().each { col, row ->
    nodes[col][row].isVisited = false
  }  
  return resultEdges
}

// 左隅を起点にして全域木(for 根->葉)を求める
def treeRoot2Leaf = createPrimSpanningTree(nodes[0][0])
// 左隅を起点にして全域木(for 葉->根)を求める
def treeLeaf2Root = createPrimSpanningTree(nodes[0][0])

// 根->葉へのパスを確定させる
treeRoot2Leaf.each { fromNode, toNode ->
  if( fromNode.col == toNode.col ) {
    if( fromNode.row + 1 == toNode.row )       fromNode.east = true
    else if( fromNode.row == toNode.row + 1 ) fromNode.west = true
    else { assert false }
  }
  else {
    if( fromNode.col + 1 == toNode.col )       fromNode.south = true
    else if( fromNode.col == toNode.col + 1 ) fromNode.north = true
    else { assert false }
  }
}

// 葉->根へのパスを確定させる
treeLeaf2Root.each { fromNode, toNode ->
  if( fromNode.col == toNode.col ) {
    if( fromNode.row + 1 == toNode.row )       toNode.west = true
    else if( fromNode.row == toNode.row + 1 ) toNode.east = true
    else { assert false }
  }
  else {
    if( fromNode.col + 1 == toNode.col )       toNode.north = true
    else if( fromNode.col == toNode.col + 1 ) toNode.south = true
    else { assert false }
  }
}

// 隣接ノードへの全有向パス数
def edge = 0
[0..<MAXCOL, 0..<MAXROW].combinations().each { col, row ->
  edge += nodes[col][row].east ? 1 : 0
  edge += nodes[col][row].west ? 1 : 0
  edge += nodes[col][row].north ? 1 : 0
  edge += nodes[col][row].south ? 1 : 0
}

// 60 隣接ノードへの全有向パス数 / 全有向パス数
assert 0.6 >= (edge / (2 * 4 + 3 * ((MAXCOL-2) * 2 + (MAXROW-2) * 2) + 4 * (MAXCOL-2) * (MAXROW-2)))

// XMLデータを出力
new StringWriter().with {
  new groovy.xml.MarkupBuilder(it).labyrinth {
    [0..<MAXCOL, 0..<MAXROW].combinations().each { col, row ->
      cell(doors: nodes[col][row].toXML(), position: "${col+1},${row+1}", "")
    }
  }
  println it.toString()
}