–Question:
–Modify the BFS algorithm to return a list of all reachable points from the start position (1, 1) in the following maze:
— Write a function reachablePoints :: Maze -> Position -> [Position].
— Example Output: For the start (1, 1), the output should be:
— [(1,1), (2,1), (3,1), (4,1), (5,1), (5,2), (5,3), (5,4), (5,5)]
type Maze = [String]
type Position = (Int, Int)
— Check if a position is valid for movement
isValid :: Maze -> Position -> Bool
isValid maze (x, y) =
x >= 0 && x < length maze &&
y >= 0 && y < length (head maze) &&
(maze !! x !! y == ‘ ‘)
— BFS to find all reachable points
reachablePoints :: Maze -> Position -> [Position]
reachablePoints maze start = bfs [start] [] []
where
— BFS function
bfs [] _ reachable = reachable
bfs (current:queue) visited reachable
| current `elem` visited = bfs queue visited reachable
| otherwise =
let (x, y) = current
neighbors = filter (isValid maze) [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
newQueue = queue ++ filter (`notElem` visited) neighbors
in bfs newQueue (current : visited) (reachable ++ [current])
sample1 = [“*********”,
“* * * *”,
“* * * * *”,
“* * * * *”,
“* * *”,
“******* *”,
” *”,
“*********”]
printMaze x =putStr (concat (map (++”\n”) x))
— 3. Count the Steps in Shortest Path
— Question:
— Write a function shortestPathLength :: Maze -> Position -> Position -> Int that returns the number of steps in the shortest path between two positions. Use the following maze:
shortestPathLength maze start end = bfs [start] 0 []–start with 0 step
where
bfs [] _ _= -1 –return -1 if there is no path
bfs (current:queue) steps visited
|current== end = steps— return the number of steps when the end is reach
|current `elem` visited =bfs queue steps visited
|otherwise =
let (x,y) =current
neighbors=filter (isValid maze) [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
newQueue= queue++ filter (`notElem` visited) neighbors
in bfs newQueue (steps +1) (current:visited)
— Write a function generateDistanceMap :: Maze -> Position -> [[Int]] that generates a grid where each cell contains the distance from the start position. Unreachable cells should contain -1. Use this maze
–Write a function isReachable :: Maze -> Position -> Position -> Bool that returns True if there is a path from the start to the goal, and False otherwise. Use the maze:
isReachable maze start goal = bfs [start] []
where
bfs [] _=False
bfs (current:queue) visited
|current ==goal = True
|current `elem` visited =bfs queue visited
|otherwise =
let (x,y) = current
neighbors=filter (isValid maze)[(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
newQueue= queue++[n|n<-neighbors, n`notElem` visited]
in bfs newQueue (current :visited)
— Write a function longestPath :: Maze -> Position -> Position -> Int that finds the longest possible path between two points in a maze. Assume the maze may have loops and cycles, and all cells are reachable.
longestPath maze start end = dfs start [] 0
where
dfs :: Position -> [Position] -> Int -> Int
dfs current visited currentLength
| current == end = currentLength — Goal reached, return the path length
| otherwise =
let (x, y) = current
neighbors = filter (`notElem` visited) $
filter (isValid maze) [(x – 1, y), (x + 1, y), (x, y – 1), (x, y + 1)]
pathLengths = [dfs n (current : visited) (currentLength + 1) | n <- neighbors]
in if null pathLengths then currentLength else maximum pathLengths
