kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

人材獲得作戦・4 試験問題 を解いてみた

なんか、人材獲得作戦・4 試験問題ほかの問題を解くのが一部で流行っているらしいので、Scalaで解いてみた。途中、くだらない所ではまって時間を浪費しまって、1時間超過してしまったのは恥ずかしい限りだ(正確には計測してないが、たぶん1時間20〜30分くらい)。もっと精進したい。普通のBFS+αで解いてみた。

import scala.io.Source
import java.io._
import scala.collection.mutable.Queue

val maze = Source.fromFile(new File("input.txt")).getLines().toList.toArray.map(_.toCharArray)
val (h, w) = (maze.length, maze(0).length)
var (x, y) = 
(for(x <- 0 until w;
    y <- 0 until h; if maze(y)(x) == 'S') yield (x, y)).toList.head
def findRoute(maze: Array[Array[Char]]): List[(Int, Int)] = {
  val visit = new Array[Array[Boolean]](maze.length, maze(0).length)
  val q = new Queue[List[(Int, Int)]]
  q += List((x, y))
  while(true) {
    for(_ <- 0 until q.size) {
      val path@((cx, cy)::_) = q.dequeue
      if(maze(cy)(cx) == 'G') return path.reverse
      if((!visit(cy)(cx)) && maze(cy)(cx) != '*') {
        visit(cy)(cx) = true
        q += ((cx + 1, cy) :: path)
        q += ((cx - 1, cy) :: path)
        q += ((cx, cy + 1) :: path)
        q += ((cx, cy - 1) :: path)
      }
    }
  }
  return null
}

def printRoute(maze: Array[Array[Char]], path: List[(Int, Int)]) {
  val answer = Set(path:_*)
  for(y <- 0 until maze.length) {
    for(x <- 0 until maze(0).length) {
      val e = maze(y)(x)
      if(e == 'S' || e == 'G' || !answer((x, y))) print(e)
      else  print("$")
    }
    println()
  }
}

printRoute(maze, findRoute(maze))

実行結果。元の解答例とは若干ルートが違うが、

  • 最短経路が複数あるときはそのうちの1つが出力されていればOK

とのことなので、これでOKだろう。

**************************
*S* * $$$$               *
*$* *$$* $*************  *
*$* $$*  $$************  *
*$$$$*    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$* $$$$$$$$$$$$$G  *
*  *  $$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************

追記:しかし、この問題が解けなかったからといって仕事でプログラム書けないかはまた別の話な気がするなー。