なんか、人材獲得作戦・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 * * * $$$$*********** * * * * ******* * * * * * **************************
追記:しかし、この問題が解けなかったからといって仕事でプログラム書けないかはまた別の話な気がするなー。