[ad_1]

I am trying to solve this maze problem using BFS algorithm. Here’s how the problem should work.

Given below is the vector of String, where **s** is the starting point and **e** is the destination. We want to find shortest path to the destination.

```
maze = [
"xxxxxxxxxxxxxxxxxx",
"x x x ex",
"x x x x xxxx",
"x x x x",
"xs x x x",
"xxxxxxxxxxxxxxxxxx"
]
```

So if the algorithms solve it correctly then it should return **Some(“rrurruurrrdddrrruuurrrr”)** where **r** denotes **right**, **l** denotes **left**, **u** denotes **up**, and **d** denotes **down**.

Here’s is my bfs algorithms:

```
def bfs[V](nbrs: V => Set[V], src: V): (Map[V, V], Map[V, Int]) = {
def expand(frontier: Set[V], parent: Map[V, V]): (Set[V], Map[V, V]) = {
val newFrontier = frontier.map(i => nbrs(i)).toList
val flatNewFrontier = newFrontier.flatten
(flatNewFrontier.filterNot(i => parent.contains(i)).toSet, parent ++ frontier.toList.flatMap(p => newFrontier(frontier.toList.indexOf(p)).map(i => i -> p).toMap))
}
@tailrec
def iterate(frontier: Set[V], parent: Map[V, V], distance: Map[V, Int], d: Int):
(Map[V, V], Map[V, Int]) =
if frontier.isEmpty then
(parent, distance)
else {
val (frontier_, parent_) = expand(frontier, parent)
val distance_ = distance ++ frontier_.foldLeft(Map.empty[V, Int])((acc, i) => acc + (i -> (d+1))) // derive new distance map
iterate(frontier_, parent ++ parent_.filterNot((k, v) => parent.contains(k)), distance_, d + 1)
}
iterate(Set(src), Map(src -> src), Map(), 0)
}
```

And this is the function maze:

```
def mazeBFS(maze: Vector[String]): Option[String] = ???
```

Thank you everyone in advance.

[ad_2]