// 1068: Maze Solver — Backtracking on 2D Grid
use std::collections::VecDeque;
const DIRS: [(i32, i32); 4] = [(0, 1), (1, 0), (0, -1), (-1, 0)];
// Approach 1: DFS backtracking
fn solve_maze(maze: &[Vec<i32>], start: (usize, usize), end_: (usize, usize)) -> Option<Vec<(usize, usize)>> {
let rows = maze.len();
let cols = maze[0].len();
let mut visited = vec![vec![false; cols]; rows];
let mut path = Vec::new();
fn dfs(
r: usize, c: usize, end_: (usize, usize),
maze: &[Vec<i32>], visited: &mut Vec<Vec<bool>>, path: &mut Vec<(usize, usize)>,
rows: usize, cols: usize,
) -> bool {
if (r, c) == end_ {
path.push((r, c));
return true;
}
if maze[r][c] == 1 || visited[r][c] { return false; }
visited[r][c] = true;
path.push((r, c));
for &(dr, dc) in &DIRS {
let nr = r as i32 + dr;
let nc = c as i32 + dc;
if nr >= 0 && nr < rows as i32 && nc >= 0 && nc < cols as i32 {
if dfs(nr as usize, nc as usize, end_, maze, visited, path, rows, cols) {
return true;
}
}
}
path.pop();
false
}
if dfs(start.0, start.1, end_, maze, &mut visited, &mut path, rows, cols) {
Some(path)
} else {
None
}
}
// Approach 2: BFS for shortest path
fn solve_maze_bfs(maze: &[Vec<i32>], start: (usize, usize), end_: (usize, usize)) -> Option<Vec<(usize, usize)>> {
let rows = maze.len();
let cols = maze[0].len();
let mut visited = vec![vec![false; cols]; rows];
let mut parent = vec![vec![(usize::MAX, usize::MAX); cols]; rows];
let mut queue = VecDeque::new();
queue.push_back(start);
visited[start.0][start.1] = true;
let mut found = false;
while let Some((r, c)) = queue.pop_front() {
if (r, c) == end_ { found = true; break; }
for &(dr, dc) in &DIRS {
let nr = r as i32 + dr;
let nc = c as i32 + dc;
if nr >= 0 && nr < rows as i32 && nc >= 0 && nc < cols as i32 {
let (nr, nc) = (nr as usize, nc as usize);
if maze[nr][nc] == 0 && !visited[nr][nc] {
visited[nr][nc] = true;
parent[nr][nc] = (r, c);
queue.push_back((nr, nc));
}
}
}
}
if !found { return None; }
let mut path = vec![end_];
let (mut r, mut c) = end_;
while (r, c) != start {
let (pr, pc) = parent[r][c];
path.push((pr, pc));
r = pr;
c = pc;
}
path.reverse();
Some(path)
}
fn main() {
let maze = vec![
vec![0, 0, 1, 0, 0],
vec![0, 0, 0, 0, 1],
vec![1, 1, 0, 1, 0],
vec![0, 0, 0, 0, 0],
vec![0, 1, 1, 0, 0],
];
if let Some(path) = solve_maze(&maze, (0, 0), (4, 4)) {
println!("DFS path: {:?}", path);
}
if let Some(path) = solve_maze_bfs(&maze, (0, 0), (4, 4)) {
println!("BFS path (shortest): {:?}", path);
}
}
#[cfg(test)]
mod tests {
use super::*;
fn test_maze() -> Vec<Vec<i32>> {
vec![
vec![0, 0, 1, 0, 0],
vec![0, 0, 0, 0, 1],
vec![1, 1, 0, 1, 0],
vec![0, 0, 0, 0, 0],
vec![0, 1, 1, 0, 0],
]
}
#[test]
fn test_dfs() {
let maze = test_maze();
let path = solve_maze(&maze, (0, 0), (4, 4)).unwrap();
assert_eq!(*path.first().unwrap(), (0, 0));
assert_eq!(*path.last().unwrap(), (4, 4));
}
#[test]
fn test_bfs() {
let maze = test_maze();
let path = solve_maze_bfs(&maze, (0, 0), (4, 4)).unwrap();
assert_eq!(*path.first().unwrap(), (0, 0));
assert_eq!(*path.last().unwrap(), (4, 4));
}
#[test]
fn test_impossible() {
let maze = vec![vec![0, 1], vec![1, 0]];
assert!(solve_maze(&maze, (0, 0), (1, 1)).is_none());
}
}
(* 1068: Maze Solver — Backtracking on 2D Grid *)
(* 0 = open, 1 = wall *)
let directions = [| (0, 1); (1, 0); (0, -1); (-1, 0) |]
(* Approach 1: Backtracking to find any path *)
let solve_maze maze start_r start_c end_r end_c =
let rows = Array.length maze in
let cols = Array.length maze.(0) in
let visited = Array.init rows (fun _ -> Array.make cols false) in
let path = ref [] in
let rec dfs r c =
if r = end_r && c = end_c then begin
path := (r, c) :: !path;
true
end else if r < 0 || r >= rows || c < 0 || c >= cols
|| maze.(r).(c) = 1 || visited.(r).(c) then false
else begin
visited.(r).(c) <- true;
path := (r, c) :: !path;
let found = ref false in
Array.iter (fun (dr, dc) ->
if not !found then
found := dfs (r + dr) (c + dc)
) directions;
if not !found then
path := List.tl !path;
!found
end
in
if dfs start_r start_c then Some (List.rev !path) else None
(* Approach 2: BFS for shortest path *)
let solve_maze_bfs maze start_r start_c end_r end_c =
let rows = Array.length maze in
let cols = Array.length maze.(0) in
let visited = Array.init rows (fun _ -> Array.make cols false) in
let parent = Array.init rows (fun _ -> Array.make cols (-1, -1)) in
let queue = Queue.create () in
Queue.push (start_r, start_c) queue;
visited.(start_r).(start_c) <- true;
let found = ref false in
while not (Queue.is_empty queue) && not !found do
let (r, c) = Queue.pop queue in
if r = end_r && c = end_c then found := true
else
Array.iter (fun (dr, dc) ->
let nr = r + dr and nc = c + dc in
if nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& maze.(nr).(nc) = 0 && not visited.(nr).(nc) then begin
visited.(nr).(nc) <- true;
parent.(nr).(nc) <- (r, c);
Queue.push (nr, nc) queue
end
) directions
done;
if not !found then None
else begin
let path = ref [(end_r, end_c)] in
let r = ref end_r and c = ref end_c in
while (!r, !c) <> (start_r, start_c) do
let (pr, pc) = parent.(!r).(!c) in
path := (pr, pc) :: !path;
r := pr; c := pc
done;
Some !path
end
let () =
let maze = [|
[|0; 0; 1; 0; 0|];
[|0; 0; 0; 0; 1|];
[|1; 1; 0; 1; 0|];
[|0; 0; 0; 0; 0|];
[|0; 1; 1; 0; 0|]
|] in
(match solve_maze maze 0 0 4 4 with
| Some path -> assert (List.hd path = (0, 0)); assert (List.nth path (List.length path - 1) = (4, 4))
| None -> assert false);
(match solve_maze_bfs maze 0 0 4 4 with
| Some path -> assert (List.hd path = (0, 0))
| None -> assert false);
(* Impossible maze *)
let maze2 = [| [|0; 1|]; [|1; 0|] |] in
assert (solve_maze maze2 0 0 1 1 = None);
Printf.printf "✓ All tests passed\n"