# Scala solution with BFS identical to supplied Java solution gets TLE

• Here's my solution, with some tweaks to attempt to make it faster.
I hit a Time Limit Exceeded. Does anyone have ideas on how to improve?

``````  def cutOffTree(forest: List[List[Int]]): Int = {
case class SearchNode(node: Node, dist: Int)
case class Tree(i: Int, j: Int, height: Int)
case class Node(i: Int, j: Int)
val diffs = Seq((-1,0), (1, 0), (0, -1), (0, 1))

val visited = Array.ofDim[Boolean](forest.length, forest(0).length)
val q = new mutable.Queue[SearchNode]()
def shortestPath(source: Node, destination: Node): Int = {
// Zero out visited
for (i <- 0 until visited.length) {
for (j <- 0 until visited(0).length) {
visited(i)(j) = false
}
}

// empty Queue
while (q.nonEmpty) q.dequeue()

println(s"Looking for sp from \$source to \$destination")

visited(source.i)(source.j) = true
q.enqueue(SearchNode(source, 0))

var dist = -1
var cont = true

while (q.nonEmpty && cont) {
val gNode = q.dequeue()

val Node(i, j) = gNode.node
val newDist = gNode.dist + 1

diffs.foreach { case (di, dj) =>
val ni = i + di
val nj = j + dj
if (
inBounds(ni, visited.length) &&
inBounds(nj, visited(0).length) &&
!visited(ni)(nj) &&
forest(ni)(nj) != 0
) {
visited(gNode.node.i)(gNode.node.j) = true

if (ni == destination.i && nj == destination.j) {
dist = newDist
cont = false
} else {
q.enqueue(SearchNode(Node(ni, nj), newDist))
}
}
}

}

dist
}

val trees = mutable.ArrayBuffer[Tree]()

for (i <- 0 until forest.length) {
for (j <- 0 until forest(0).length) {
if (forest(i)(j) > 1) trees.append(Tree(i, j, forest(i)(j)))
}
}

val nodeOrder = trees.sortBy(_.height).map { case Tree(i, j, _) => Node(i, j) }

var ans = 0
var curr = Node(0, 0)
var cont = true
for (i <- 0 until nodeOrder.length if cont) {
val next = nodeOrder(i)
val sp = if (curr == next) 0 else shortestPath(curr, next)
if (sp != -1) {
ans += sp
curr = next
} else {
ans = -1
cont = false
}
}

ans
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.