-- 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 :: [Position] -> [Position] -> [Position] -> [Position]
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 :: Maze
sample1 =
[ "*********"
, "* * * *"
, "* * * * *"
, "* * * * *"
, "* * *"
, "******* *"
, " *"
, "*********"
]
printMaze :: Maze -> IO ()
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 -> Position -> Position -> Int
shortestPathLength maze start end = bfs [start] 0 []
where
bfs :: [Position] -> Int -> [Position] -> Int
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 reached
| 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
-- (Chức năng generateDistanceMap chưa được cung cấp trong yêu cầu ban đầu)
-- 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 -> Position -> Position -> Bool
isReachable maze start goal = bfs [start] []
where
bfs :: [Position] -> [Position] -> Bool
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 -> Position -> Position -> Int
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
-- Hàm main để chạy chương trình và kiểm tra các hàm
main :: IO ()
main = do
putStrLn "Maze:"
printMaze sample1
let start = (1, 1)
let reachable = reachablePoints sample1 start
putStrLn "\nReachable Points from (1,1):"
print reachable
let end = (5, 5)
let steps = shortestPathLength sample1 start end
putStrLn $ "\nShortest path length from " ++ show start ++ " to " ++ show end ++ ": " ++ show steps
let reachableCheck = isReachable sample1 start end
putStrLn $ "\nIs reachable from " ++ show start ++ " to " ++ show end ++ ": " ++ show reachableCheck
let longest = longestPath sample1 start end
putStrLn $ "\nLongest path length from " ++ show start ++ " to " ++ show end ++ ": " ++ show longest
Result
Maze:
*********
* * * *
* * * * *
* * * * *
* * *
******* *
*
*********
Reachable Points from (1,1):
[(1,1),(2,1),(3,1),(4,1),(4,2),(4,3),(3,3),(2,3),(1,3),(1,4),(1,5),(2,5),(3,5),(4,5),(4,6),(4,7),(3,7),(5,7),(2,7),(6,7),(1,7),(6,6),(6,5),(6,4),(6,3),(6,2),(6,1),(6,0)]
Shortest path length from (1,1) to (5,5): -1
Is reachable from (1,1) to (5,5): False
Longest path length from (1,1) to (5,5): 24