Assume you have a 2D array that represents a maze. Spaces are denoted by a 0 and walls are denoted by a 1. Devise the most efficient way to get through this maze, while following these two simple rules:
- You can only move right (not left)
- You can only move down (not up)
My solution in Scala:
package mazesolver case class Pos( x: Int, y: Int){ def move(m: Move):Pos = m match { case Right => Pos(x+1, y) case Down => Pos(x, y+1) } } class Move case object Right extends Move case object Down extends Move object Solver { def solve( maze: Maze, start: Pos, end: Pos): List[Move] = { def canMove( p:Pos, m: Move ): Boolean = { val newPos = p.move(m) if( newPos.x < 0 || newPos.y < 0 || newPos.y >= maze.size || newPos.x >= maze(newPos.y).size || maze(newPos.y)(newPos.x) == 1 ) false else true } def findPathFrom( curr: Pos, moves: List[Move] ):List[Move] = if ( curr == end) moves.reverse else{ val pathR= if (canMove( curr, Right) ) findPathFrom( curr.move(Right), Right::moves) else Nil val pathD = if (canMove( curr, Down) ) findPathFrom( curr.move(Down), Down::moves) else Nil if( pathR == Nil ) pathD else pathR } findPathFrom( start, Nil) } }
Комментариев нет:
Отправить комментарий