Maze Solver

In this challenge, you will implement a maze solver in Rust. A maze can be represented as a grid where each cell is either an open path or a wall. The goal is to navigate from a starting point to an ending point using the shortest path possible. This problem will test your understanding of control flow in Rust, including loops, conditionals, and possibly recursion.

Your Task

Your task is to write a function solve_maze that takes a 2D vector of characters representing the maze and two tuples representing the start and end points. The maze will be given as a grid of characters where 'S' represents the start, 'E' represents the end, '.' represents an open path, and '#' represents a wall.

The function should return a vector of tuples representing the path from start to end if a path exists, or an empty vector if no path exists.

Constraints

The maze will always contain exactly one 'S' and one 'E'.
You can only move up, down, left, or right.
Implement the function using appropriate control flow constructs (loops, conditionals, and/or recursion).
Ensure your solution handles edge cases, such as no available path or mazes with various sizes.
If the maze is a dead-end, return an empty vector.
If the maze has multiple solutions, return the shortest path.

Example

let maze = vec![
    vec!['S', '.', '#', '#', '#'],
    vec!['#', '.', '#', '.', '.'],
    vec!['#', '.', '.', '.', '#'],
    vec!['#', '#', '#', '.', '#'],
    vec!['#', '#', '#', 'E', '#']
];
let start = (0, 0);
let end = (4, 3);
 
let path = solve_maze(maze, start, end);
assert_eq!(
    path,
    vec![
        (0, 0), // starting point
        (0, 1), // right
        (1, 1), // down
        (2, 1), // down
        (2, 2), // right
        (2, 3), // right
        (3, 3), // down
        (4, 3) // down
    ]
);

In the example above, we start from 'S' at (0, 0), the first move would be going to the right (0, 1), then down (1, 1), and so on until we reach the end at (4, 3).

Did You Know?

Maze solving algorithms are not just for games. They are used in robotics for pathfinding, in computer networks for routing, and in various optimization problems. Algorithms such as Depth-First Search (DFS), Breadth-First Search (BFS), and A* are commonly used to solve these problems efficiently.

Hints

Collections:
- VecDeque: A double-ended queue from the std::collections module, which is useful for implementing a queue for BFS. Methods like push_back and pop_front will be helpful.
Indexing:
- Use usize for indices and be cautious with arithmetic operations to avoid overflow. The wrapping_add method can help with safe arithmetic.
2D Vector Initialization:
- Initialize 2D vectors for visited and path tracking. Use nested vec! macros for creating the initial structure.
Backtracking Path:
- Once the end point is reached, backtrack using the path vector to reconstruct the path from end to start. Collect these coordinates in a vector and reverse it to get the path from start to end.
Boundary Checks:
- Ensure the new coordinates are within the maze boundaries and check if the cell is a wall ('#') or already visited.

Editor not available on Mobile!

In order to solve the challenge, please visit this page on a desktop computer.

Solutions

LeonardoPinheiro23

8 days ago

4.96ms

88.63kb

use std::usize;
#[derive(Debug)]
struct Points;
impl Points {
    fn adjacent_points(
        (x, y): (usize, usize),
        (max_x, max_y): (usize, usize)
    ) ->  Vec<(usize, usize)> {
        let mut neighbors = Vec::with_capacity(4);
        if x > 0 {
            neighbors.push((x - 1, y)); // left
        }
        if x + 1 <= max_x {
            neighbors.push((x + 1, y)); // right
        }
        if y > 0 {
            neighbors.push((x, y - 1)); // up
        }
        if y + 1 <= max_y {
            neighbors.push((x, y + 1)); // down
        }
        neighbors
    }
    fn is_open_point(&(x, y): &(usize, usize), maze: &Vec<Vec<char>>) -> bool {
        let char_in_position = *maze.get(x).unwrap().get(y).unwrap();
        
        char_in_position == '.' || char_in_position == 'E' || char_in_position == 'S'
    }
    fn is_end_point(&(x, y): &(usize, usize), maze: &Vec<Vec<char>>) -> bool {
        let char_in_position = *maze.get(x).unwrap().get(y).unwrap();
        char_in_position == 'E'
    }
}
#[derive(Debug, Default, Clone)]
struct Path(Vec<(usize, usize)>);
impl Path {
    fn new(start: (usize, usize)) -> Self {
        Path(vec![start])
    }
    fn last(&self) -> &(usize, usize) {
        self.0.last().unwrap()
    }
    fn push(&mut self, point: (usize, usize)) {
        self.0.push(point);
    }
    fn get_valid_path_positions(
        &self,
        maze: &Vec<Vec<char>>,
        max_point: (usize, usize)
    ) -> Vec<(usize, usize)> {
        let mut adjacent_positions = Points::adjacent_points(*self.last(), max_point);
    
        adjacent_positions.retain(|point|
            Points::is_open_point(point, maze) && !self.0.contains(point)
        );
        adjacent_positions
    }
    fn has_valid_path_positions(
        &self,
        maze: &Vec<Vec<char>>,
        max_point: (usize, usize)
    ) -> bool {
        
        Points::adjacent_points(*self.last(), max_point)
            .into_iter()
            .any(|point| Points::is_open_point(&point, maze) && !self.0.contains(&point))
    }
    fn to_vec(self) -> Vec<(usize, usize)> {
        self.0
    }
}
#[derive(Debug)]
struct MazeSolver{
    max_point: (usize, usize),
    paths: Vec<Path>,
    maze: Vec<Vec<char>>,
}
impl MazeSolver {
    fn new(maze: Vec<Vec<char>>, start: (usize, usize)) -> Self {
        MazeSolver {
            max_point: (maze.len() - 1, maze.first().unwrap().len() - 1),
            paths: vec![Path::new(start)],
            maze
        }
    }
    fn update_paths(&mut self) {
        // 1. Remove any paths that no longer have valid adjacent positions in the maze.
        self.paths.retain(|path| path.has_valid_path_positions(&self.maze, self.max_point));
        // 2. For each remaining path, collect a list of its new valid adjacent positions.
        let mut new_points_per_path: Vec<Vec<(usize, usize)>> = self.paths
            .iter()
            .map(|path| path.get_valid_path_positions(&self.maze, self.max_point))
            .collect();
        // 3. Save the current number of valid paths.
        let old_len: usize = new_points_per_path.len();
        // 4. Calculate the total number of new paths we’ll need based on the number of valid moves.
        let new_len: usize = new_points_per_path.iter().map(|vec| vec.len()).sum();
        // 5. Extend the `paths` vector with default `Path`s to make room for new forks.
        self.paths.resize_with(new_len, || Path::default());
        // 6. Split the vector into mutable slices:
        //    - `old_paths`: the original paths we’re updating
        //    - `new_paths`: the placeholder `Path::default()` items we’ll overwrite with forks
        let (old_paths, new_paths) = self.paths.split_at_mut(old_len);
        let mut new_paths_index = 0;
        // 7. Iterate over the original paths
        for index in 0..old_len {
            // Take the new positions for this path
            let new_path_points = &mut new_points_per_path[index];
            let points_count = new_path_points.len();
            let path = &mut old_paths[index];
            // If there are multiple valid positions, clone this path into forks
            // and assign one new position to each new path.
            if points_count != 1 {
                for _ in 1..points_count {
                    let mut path_clone = path.clone();
                    path_clone.push(new_path_points.pop().unwrap());
                    new_paths[new_paths_index] = path_clone;
                    new_paths_index += 1;
                }
            }
            // Add the last new position to the original path.
            path.push(new_path_points.pop().unwrap());
        }
    }
    fn has_reached_end_point(&self) -> bool {
        self.paths.iter().any(|path| Points::is_end_point(path.last(), &self.maze))
    }
    fn solve_maze(mut self) -> Option<Path> {
        loop {
            self.update_paths();
            if self.paths.is_empty() {
                return None;
            }
            if self.has_reached_end_point() {
                return self.paths.into_iter().find(|path|
                    Points::is_end_point(path.last(), &self.maze)
                );
            }
        }
    }
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    _end: (usize, usize),
) -> Vec<(usize, usize)> {
    let maze_solver = MazeSolver::new(maze, start);
    
    match maze_solver.solve_maze() {
        Some(path) => path.to_vec(),
        None => Vec::new(),
    } 
}

Tommytto

18 days ago

6.34ms

91.40kb

use std::collections::{HashMap, HashSet, VecDeque};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let directions: Vec<(isize, isize)> = vec![(-1, 0), (0, -1), (1, 0), (0, 1)];
    // Your code here
    // what we can do
    // list of all nodes and their distances
    // start point is zero
    // check neighbours, updates their distances
    // go to neighbour 
    let mut dist_map = HashMap::new();
    let mut visited = HashSet::new();
    for x in 0..maze.len() {
        for y in 0..maze[0].len() {
            dist_map.insert((x, y), 999);
        }
    }
    dist_map.insert(start, 0);
    let mut queue = VecDeque::new();
    queue.push_back(start);
    visited.insert(start);
    while !queue.is_empty() {
        let Some(item) = queue.pop_front() else {
            return vec![];
        };
        if item == end {
            break;
        }
        for dir in &directions {
            
            let (x, y) = item;
            let (dx, dy) = dir;
            let (x2, y2) = (x as isize + dx, y as isize + dy);
            if x2 < 0 || x2 >= (maze.len() as isize) || y2 < 0 || y2 >= (maze[0].len() as isize) {
                continue;
            }
            let (x2, y2) = (x2 as usize, y2 as usize);
            if visited.contains(&(x2, y2)) {
                continue;
            }
            visited.insert((x2, y2));
            if maze[x2][y2] == '#' {
                continue;
            }
            let p1_dist = dist_map.get(&(x, y)).expect("dist should exists for every node");
            let p2_dist = p1_dist + 1;
            queue.push_back((x2, y2));
            dist_map.insert((x2, y2), p2_dist);
            if (x2, y2) == end {
                queue.clear();
                break;
            }
        }
    }
    if *dist_map.get(&end).unwrap() == 999 {
        return vec![];
    }
    let mut path = vec![];
    let mut cur = end;
    loop {
        path.push(cur);
        if cur == start {
            break;
        }
        let (x, y) = cur;
        let cur_dist = dist_map.get(&cur).expect("dist map should have current");
        for (dx, dy) in &directions {
            let new_p = ((x as isize + dx) as usize, (y as isize + dy) as usize);
            let Some(dist) = dist_map.get(&new_p) else {
                continue;
            };
            if cur_dist - 1 == *dist {
                cur = new_p;
                break;
            }
        }
    }
    println!("{:?}", dist_map);
    path.reverse();
    return path
}

syberianbull

a month ago

3.82ms

89.03kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let maze_rows = maze.len();
    let maze_cols = maze[0].len();
    let mut paths = vec![vec![start]];
    let mut temp_paths: Vec<Vec<(usize, usize)>> = vec![];
    let offset: Vec<(isize, isize)> = vec![(1, 0), (0, 1), (-1, 0), (0, -1)];
    let mut last_in_path: (usize, usize);
    let mut test_row_i: isize;
    let mut test_col_i: isize;
    let mut test_row: usize;
    let mut test_col: usize;
    let mut test_trues: Vec<usize> = vec![];
    let mut k: usize;
    let mut test_char: char;
    while paths.len() > 0 {
        for path in paths {
            last_in_path = *path.last().clone().unwrap();
            for (j, off) in offset.iter().enumerate() {
                test_row_i = last_in_path.0 as isize + off.0;
                test_col_i = last_in_path.1 as isize + off.1;
                if !(test_row_i < 0 || test_col_i < 0) {
                    test_row = test_row_i as usize;
                    test_col = test_col_i as usize;
                    if !(test_row >= maze_rows || test_col >= maze_cols)
                        && !(path.contains(&(test_row, test_col)))
                    {
                        test_char = maze[test_row][test_col];
                        match test_char {
                            '.' => test_trues.push(j),
                            'E' => {
                                temp_paths.clear();
                                temp_paths.push(path.clone());
                                temp_paths[0].push((test_row, test_col));
                                return temp_paths[0].clone();
                            }
                            __ => (),
                        }
                    }
                }
            }
            while test_trues.len() > 0 {
                k = test_trues.pop().unwrap();
                temp_paths.push(path.clone());
                temp_paths.last_mut().unwrap().push((
                    (last_in_path.0 as isize + offset[k].0) as usize,
                    (last_in_path.1 as isize + offset[k].1) as usize,
                ));
            }
        }
        paths = temp_paths.clone();
        temp_paths.clear();
    }
    return vec![];
}

Hung Dinh

nhdinh

2 months ago

5.73ms

90.86kb

fn solve(
    maze: &Vec<Vec<char>>,
    dim: &(usize, usize),
    mut seen: Vec<Vec<u8>>,
    start: &(usize, usize),
    end: &(usize, usize),
) -> Option<Vec<(usize, usize)>> {
    if start == end {
        return Some(vec![*end]);
    }
    let start_i32 = (start.0 as i32, start.1 as i32);
    let directions = vec![
        (start_i32.0 - 1, start_i32.1),
        (start_i32.0 + 1, start_i32.1),
        (start_i32.0, start_i32.1 + 1),
        (start_i32.0, start_i32.1 - 1),
    ];
    let mut ans: Vec<(usize, usize)> = vec![*start];
    seen[start.0][start.1] = 0; // mark that cannot go any further
    let mut found: bool = false;
    for dir in directions.iter() {
        if dir.0 >= 0
            && (dir.0 as usize) < dim.0
            && dir.1 >= 0
            && (dir.1 as usize) < dim.1
            && seen[dir.0 as usize][dir.1 as usize] == 1
        {
            if let Some(tmp_ans) = solve(
                maze,
                dim,
                seen.clone(),
                &(dir.0 as usize, dir.1 as usize),
                end,
            ) {
                ans.extend(tmp_ans.iter());
                found = true;
            }
        }
    }
    if found {
        Some(ans)
    } else {
        None
    }
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let rows = maze.len();
    let cols = maze[0].len();
    let mut seen: Vec<Vec<u8>> = vec![vec![1; cols]; rows];
    seen[start.0][end.0] = 0;
    for r in 0..rows {
        for c in 0..cols {
            if maze[r][c] == '#' {
                seen[r][c] = 0;
            }
        }
    }
    for _r in seen.iter() {
        println!("{_r:?}");
    }
    if let Some(ans) = solve(&maze, &(rows, cols), seen.clone(), &start, &end) {
        ans
    } else {
        vec![]
    }
}

Jakub Wiśniewski

wisniewskij

2 months ago

4.71ms

89.06kb

enum Direction {
        Right,
        Back,
        Left,
        Front,
    }
    struct PathFinder<'a> {
        path: Vec<(usize, usize)>,
        position: (usize, usize),
        maze: &'a Vec<Vec<char>>,
        path_to_exit: Option<Vec<(usize, usize)>>,
        dead_end: bool
    }
    impl<'a> PathFinder<'a> {
        fn new(
            maze: &'a Vec<Vec<char>>,
            position: (usize, usize),
            path: Vec<(usize, usize)>,
        ) -> Self {
            Self {
                path,
                position,
                maze,
                path_to_exit: None,
                dead_end: false
            }
        }
        fn get_path_to_exit(&self) -> Option<Vec<(usize, usize)>> {
            self.path_to_exit.clone()
        }
        fn move_to_position(&mut self, position: (usize, usize)) {
            self.path.push(position);
            self.position = position;
        }
        fn check_next(&mut self, direction: Direction) -> Option<(usize, usize)> {
            let current = self.get_current_position();
            match direction {
                Direction::Right => {
                    if current.1 == 0 {
                        return None;
                    }
                }
                Direction::Back => {
                    if current.0 == self.maze.len() {
                        return None;
                    }
                }
                Direction::Left => {
                    if current.1 == self.maze[current.0].len() - 1 {
                        return None;
                    }
                }
                Direction::Front => {
                    if current.0 == 0 {
                        return None;
                    }
                }
            }
            let next_position = match direction {
                Direction::Right => (current.0, current.1 - 1),
                Direction::Back => (current.0 + 1, current.1),
                Direction::Left => (current.0, current.1 + 1),
                Direction::Front => (current.0 - 1, current.1),
            };
            if let Some(y) = self.maze.get(next_position.0) {
                if let Some(x) = y.get(next_position.1) {
                    if self.path.len() > 1 && next_position == self.path[self.path.len() - 2] {
                        return None;
                    }
                    match x {
                        'E' => {
                            let mut path = self.get_path().clone();
                            path.push(next_position);
                            self.path_to_exit = Some(path);
                            Some(next_position)
                        }
                        '.' => Some(next_position),
                        _ => None,
                    }
                } else {
                    None
                }
            } else {
                None
            }
        }
        fn next_steps(&mut self) -> Vec<(usize, usize)> {
            let mut next_possible_steps: Vec<(usize, usize)> = vec![];
            if let Some(position) = self.check_next(Direction::Left) {
                next_possible_steps.push(position);
            }
            if let Some(position) = self.check_next(Direction::Right) {
                next_possible_steps.push(position);
            }
            if let Some(position) = self.check_next(Direction::Front) {
                next_possible_steps.push(position);
            }
            if let Some(position) = self.check_next(Direction::Back) {
                next_possible_steps.push(position);
            }
            next_possible_steps
        }
        fn get_current_position(&self) -> (usize, usize) {
            self.position
        }
        fn get_path(&self) -> Vec<(usize, usize)> {
            self.path.clone()
        }
    }
    pub fn solve_maze(maze: Vec<Vec<char>>, start: (usize, usize), _end: (usize, usize)) -> Vec<(usize, usize)> {
        let mut path_finders: Vec<PathFinder> = vec![PathFinder::new(&maze, start, vec![start])];
        let mut path_to_exit: Vec<(usize, usize)> = vec![];
        let mut is_finished = false;
        loop {
            let mut new_path_finders: Vec<PathFinder> = vec![];
            let is_all_dead = path_finders.iter().all(|path_finder|{
                path_finder.dead_end
            });
            if is_all_dead {
                path_to_exit = vec![];
                break;
            }
            path_finders.iter_mut().for_each(|path_finder| {
                let next_steps = path_finder.next_steps();
                if next_steps.len() == 1 {
                    path_finder.move_to_position(next_steps[0]);
                    if let Some(path) = path_finder.get_path_to_exit() {
                        path_to_exit = path;
                        is_finished =true;
                    }
                } else if  next_steps.len() == 0 {
                    path_finder.dead_end = true;
                } else {
                    for next_step in next_steps {
                        let mut new_path = path_finder.get_path().clone();
                        new_path.push(next_step);
                        new_path_finders.push(PathFinder::new(&maze, next_step, new_path));
                        if let Some(path) = path_finder.get_path_to_exit() {
                            path_to_exit = path;
                            is_finished = true;
                            break;
                        }
                    }
                }
            });
            if new_path_finders.len() != 0 {
                path_finders = new_path_finders;
            }
            if is_finished {
                break;
            }
        }
        path_to_exit
    }

Aurimas Kuniutis

auriku

2 months ago

3.51ms

89.06kb

    enum Direction {
        Right,
        Back,
        Left,
        Front,
    }
    struct PathFinder<'a> {
        path: Vec<(usize, usize)>,
        position: (usize, usize),
        maze: &'a Vec<Vec<char>>,
        path_to_exit: Option<Vec<(usize, usize)>>,
        dead_end: bool
    }
    impl<'a> PathFinder<'a> {
        fn new(
            maze: &'a Vec<Vec<char>>,
            position: (usize, usize),
            path: Vec<(usize, usize)>,
        ) -> Self {
            Self {
                path,
                position,
                maze,
                path_to_exit: None,
                dead_end: false
            }
        }
        fn get_path_to_exit(&self) -> Option<Vec<(usize, usize)>> {
            self.path_to_exit.clone()
        }
        fn move_to_position(&mut self, position: (usize, usize)) {
            self.path.push(position);
            self.position = position;
        }
        fn check_next(&mut self, direction: Direction) -> Option<(usize, usize)> {
            let current = self.get_current_position();
            match direction {
                Direction::Right => {
                    if current.1 == 0 {
                        return None;
                    }
                }
                Direction::Back => {
                    if current.0 == self.maze.len() {
                        return None;
                    }
                }
                Direction::Left => {
                    if current.1 == self.maze[current.0].len() - 1 {
                        return None;
                    }
                }
                Direction::Front => {
                    if current.0 == 0 {
                        return None;
                    }
                }
            }
            let next_position = match direction {
                Direction::Right => (current.0, current.1 - 1),
                Direction::Back => (current.0 + 1, current.1),
                Direction::Left => (current.0, current.1 + 1),
                Direction::Front => (current.0 - 1, current.1),
            };
            if let Some(y) = self.maze.get(next_position.0) {
                if let Some(x) = y.get(next_position.1) {
                    if self.path.len() > 1 && next_position == self.path[self.path.len() - 2] {
                        return None;
                    }
                    match x {
                        'E' => {
                            let mut path = self.get_path().clone();
                            path.push(next_position);
                            self.path_to_exit = Some(path);
                            Some(next_position)
                        }
                        '.' => Some(next_position),
                        _ => None,
                    }
                } else {
                    None
                }
            } else {
                None
            }
        }
        fn next_steps(&mut self) -> Vec<(usize, usize)> {
            let mut next_possible_steps: Vec<(usize, usize)> = vec![];
            if let Some(position) = self.check_next(Direction::Left) {
                next_possible_steps.push(position);
            }
            if let Some(position) = self.check_next(Direction::Right) {
                next_possible_steps.push(position);
            }
            if let Some(position) = self.check_next(Direction::Front) {
                next_possible_steps.push(position);
            }
            if let Some(position) = self.check_next(Direction::Back) {
                next_possible_steps.push(position);
            }
            next_possible_steps
        }
        fn get_current_position(&self) -> (usize, usize) {
            self.position
        }
        fn get_path(&self) -> Vec<(usize, usize)> {
            self.path.clone()
        }
    }
    pub fn solve_maze(maze: Vec<Vec<char>>, start: (usize, usize), _end: (usize, usize)) -> Vec<(usize, usize)> {
        let mut path_finders: Vec<PathFinder> = vec![PathFinder::new(&maze, start, vec![start])];
        let mut path_to_exit: Vec<(usize, usize)> = vec![];
        let mut is_finished = false;
        loop {
            let mut new_path_finders: Vec<PathFinder> = vec![];
            let is_all_dead = path_finders.iter().all(|path_finder|{
                path_finder.dead_end
            });
            if is_all_dead {
                path_to_exit = vec![];
                break;
            }
            path_finders.iter_mut().for_each(|path_finder| {
                let next_steps = path_finder.next_steps();
                if next_steps.len() == 1 {
                    path_finder.move_to_position(next_steps[0]);
                    if let Some(path) = path_finder.get_path_to_exit() {
                        path_to_exit = path;
                        is_finished =true;
                    }
                } else if  next_steps.len() == 0 {
                    path_finder.dead_end = true;
                } else {
                    for next_step in next_steps {
                        let mut new_path = path_finder.get_path().clone();
                        new_path.push(next_step);
                        new_path_finders.push(PathFinder::new(&maze, next_step, new_path));
                        if let Some(path) = path_finder.get_path_to_exit() {
                            path_to_exit = path;
                            is_finished = true;
                            break;
                        }
                    }
                }
            });
            if new_path_finders.len() != 0 {
                path_finders = new_path_finders;
            }
            if is_finished {
                break;
            }
        }
        path_to_exit
    }

Robbie K

va1ha11a

3 months ago

4.99ms

89.28kb

use std::collections::{HashSet, VecDeque};
#[derive(Clone)]
struct PossiblePath {
    path: Vec<(usize, usize)>,
    current: (usize, usize),
}
impl PossiblePath {
    fn new(path: Vec<(usize, usize)>, current: (usize, usize)) -> Self {
        PossiblePath { path, current }
    }
    fn add_step(&mut self, next: (usize, usize)) {
        self.path.push(next);
        self.current = next;
    }
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut visited: HashSet<(usize, usize)> = HashSet::new();
    let mut queue: VecDeque<PossiblePath> = VecDeque::new();
    let mut found: Vec<(usize, usize)> = vec![];
    let fisrt_node = PossiblePath::new(vec![start], start);
    queue.push_back(fisrt_node);
    while queue.len() > 0 {
        let current_path = queue.pop_front();
        if let None = current_path {
            break;
        };
        let path = current_path.unwrap();
        let possible_next_moves = get_possible_moves(&maze, path.current, &visited);
        possible_next_moves.iter().for_each(|next_move| {
            let mut new_path = path.clone();
            new_path.add_step(*next_move);
            if *next_move == end {
                found = new_path.path;
                return;
            }
            visited.insert(*next_move);
            queue.push_back(new_path);
        });
        if found.len() > 0 {
            break;
        }
    }
    found
}
fn get_possible_moves(
    maze: &Vec<Vec<char>>,
    current: (usize, usize),
    visited: &HashSet<(usize, usize)>,
) -> Vec<(usize, usize)> {
    let maze_width = maze[0].len();
    let maze_height = maze.len();
    let all_potential: Vec<(Option<usize>, Option<usize>)> = vec![
        (current.0.checked_sub(1), Some(current.1)),
        (current.0.checked_add(1), Some(current.1)),
        (Some(current.0), current.1.checked_sub(1)),
        (Some(current.0), current.1.checked_add(1)),
    ];
    all_potential
        .iter()
        .filter(|(x, y)| {
            if (*x == None) | (*y == None) {
                false
            } else {
                true
            }
        })
        .map(|(x, y)| (x.unwrap(), y.unwrap()))
        .filter(|(x, y)| *x < maze_height && *y < maze_width)
        .filter(|(x, y)| !visited.contains(&(*x, *y)))
        .filter(|(x, y)| maze[*x][*y] != '#')
        .collect()
}

VerweyFr

3 months ago

4.47ms

89.35kb

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path = Vec::new();
    let rows = maze.len();
    let cols = maze[0].len();
    
    let mut visited = vec![vec![false; cols]; rows];
    let mut parent = vec![vec![None; cols]; rows];
    let mut queue = VecDeque::new();
    queue.push_back(start);
    visited[start.0][start.1] = true;
    while let Some((x, y)) = queue.pop_front() {
        if (x, y) == end {
            let mut current = (x, y);
            while let Some(prev) = parent[current.0][current.1] {
                path.push(current);
                current = prev;
            }
            path.push(start);
            path.reverse();
            
            // Ensure the final destination is 'E', otherwise clear the path
            if maze[end.0][end.1] != 'E' {
                path.clear();
            }
            
            return path;
        }
        let directions = [
            x.checked_sub(1).map(|nx| (nx, y)), // Up
            (x + 1 < rows).then(|| (x + 1, y)), // Down
            y.checked_sub(1).map(|ny| (x, ny)), // Left
            (y + 1 < cols).then(|| (x, y + 1)), // Right
        ];
        for &neighbor in &directions {
            if let Some((nx, ny)) = neighbor {
                if !visited[nx][ny] && matches!(maze[nx][ny], '.' | 'E') {
                    queue.push_back((nx, ny));
                    visited[nx][ny] = true;
                    parent[nx][ny] = Some((x, y));
                }
            }
        }
    }
    
    // If no valid path is found, return an empty path
    Vec::new()
}

Yixian Du

duyixian1234

3 months ago

7.00ms

89.41kb

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let rows = maze.len();
    if rows == 0 {
        return Vec::new();
    }
    let cols = maze[0].len();
    let mut visited = vec![vec![false; cols]; rows];
    let mut parent = vec![vec![None; cols]; rows];
    let mut queue = VecDeque::new();
    visited[start.0][start.1] = true;
    queue.push_back(start);
    let directions = vec![
        (-1, 0),
        (1, 0),
        (0, -1),
        (0, 1),
    ];
    while let Some((r, c)) = queue.pop_front() {
        if (r, c) == end {
            let mut path = vec![];
            let mut current = (r, c);
            path.push(current);
            while let Some(prev) = parent[current.0][current.1] {
                current = prev;
                path.push(current);
            }
            path.reverse();
            return path;
        }
        for (dr, dc) in &directions {
            let new_r = r as isize + dr;
            let new_c = c as isize + dc;
            if new_r < 0 || new_r >= rows as isize || new_c < 0 || new_c >= cols as isize {
                continue;
            }
            let new_r = new_r as usize;
            let new_c = new_c as usize;
            if maze[new_r][new_c] == '#' || visited[new_r][new_c] {
                continue;
            }
            visited[new_r][new_c] = true;
            parent[new_r][new_c] = Some((r, c));
            queue.push_back((new_r, new_c));
        }
    }
    Vec::new()
}

Anna Komarova

Vlasanya

3 months ago

4.21ms

89.41kb

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let rows = maze.len();
    if rows == 0 {
        return Vec::new();
    }
    let cols = maze[0].len();
    let mut visited = vec![vec![false; cols]; rows];
    let mut parent = vec![vec![None; cols]; rows];
    let mut queue = VecDeque::new();
    visited[start.0][start.1] = true;
    queue.push_back(start);
    let directions = vec![
        (-1, 0),
        (1, 0),
        (0, -1),
        (0, 1),
    ];
    while let Some((r, c)) = queue.pop_front() {
        if (r, c) == end {
            let mut path = vec![];
            let mut current = (r, c);
            path.push(current);
            while let Some(prev) = parent[current.0][current.1] {
                current = prev;
                path.push(current);
            }
            path.reverse();
            return path;
        }
        for (dr, dc) in &directions {
            let new_r = r as isize + dr;
            let new_c = c as isize + dc;
            if new_r < 0 || new_r >= rows as isize || new_c < 0 || new_c >= cols as isize {
                continue;
            }
            let new_r = new_r as usize;
            let new_c = new_c as usize;
            if maze[new_r][new_c] == '#' || visited[new_r][new_c] {
                continue;
            }
            visited[new_r][new_c] = true;
            parent[new_r][new_c] = Some((r, c));
            queue.push_back((new_r, new_c));
        }
    }
    Vec::new()
}

Icarus

IcarusxB

3 months ago

10.42ms

89.14kb

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let rows = maze.len();
    let cols = maze[0].len();
    
    let directions = vec![
        (-1, 0), 
        (1, 0),
        (0, -1), 
        (0, 1), 
    ];
    let mut queue = VecDeque::new();
    let mut visited = vec![vec![false; cols]; rows];
    queue.push_back((start, vec![start]));
    visited[start.0][start.1] = true;
    while let Some((current_pos, path)) = queue.pop_front() {
        let (current_row, current_col) = current_pos;
        if current_pos == end {
            return path;
        }
        for (dr, dc) in &directions {
            let new_row = current_row as isize + dr;
            let new_col = current_col as isize + dc;
            if new_row >= 0 && new_row < rows as isize && new_col >= 0 && new_col < cols as isize {
                let new_row = new_row as usize;
                let new_col = new_col as usize;
                if maze[new_row][new_col] != '#' && !visited[new_row][new_col] {
                    visited[new_row][new_col] = true;
                    let mut new_path = path.clone();
                    new_path.push((new_row, new_col));
                    queue.push_back(((new_row, new_col), new_path));
                }
            }
        }
    }
    vec![]
}

Ayushman Rathore

Spartan09

4 months ago

4.20ms

89.40kb

use std::collections::{HashMap, HashSet, VecDeque};
pub enum MazeError {
    EmptyMaze,
    InvalidDimensions,
    InvalidStartPosition,
    InvalidEndPosition,
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    if let Err(_) = validate_maze(&maze, start, end) {
        return vec![];
    }
    let n_rows = maze.len();
    let n_cols = maze[0].len();
    let mut visited: HashSet<(usize, usize)> = HashSet::new();
    let mut parent: HashMap<(usize, usize), (usize, usize)> = HashMap::new();
    let mut queue = VecDeque::new();
    queue.push_back(start);
    visited.insert(start);
    while let Some((row, col)) = queue.pop_front() {
        if (row, col) == end {
            return reconstruct_path(&parent, start, end);
        }
        let neighbors = get_valid_neighbors(row, col, n_rows, n_cols, &maze);
        for next_pos in neighbors {
            if !visited.contains(&next_pos) {
                visited.insert(next_pos);
                queue.push_back(next_pos);
                parent.insert(next_pos, (row, col));
            }
        }
    }
    vec![]
}
fn validate_maze(
    maze: &Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Result<(), MazeError> {
    if maze.is_empty() {
        return Err(MazeError::EmptyMaze);
    }
    let n_rows = maze.len();
    let n_cols = maze[0].len();
    if maze.iter().any(|row| row.len() != n_cols) {
        return Err(MazeError::InvalidDimensions);
    }
    if start.0 >= n_rows || start.1 >= n_cols || maze[start.0][start.1] == '#' {
        return Err(MazeError::InvalidStartPosition);
    }
    if end.0 >= n_rows || end.1 >= n_cols || maze[end.0][end.1] == '#' {
        return Err(MazeError::InvalidEndPosition);
    }
    Ok(())
}
fn get_valid_neighbors(
    row: usize,
    col: usize,
    n_rows: usize,
    n_cols: usize,
    maze: &Vec<Vec<char>>,
) -> Vec<(usize, usize)> {
    let mut neighbors = Vec::new();
    if row > 0 && maze[row - 1][col] != '#' {
        neighbors.push((row - 1, col));
    }
    if row + 1 < n_rows && maze[row + 1][col] != '#' {
        neighbors.push((row + 1, col));
    }
    if col > 0 && maze[row][col - 1] != '#' {
        neighbors.push((row, col - 1));
    }
    if col + 1 < n_cols && maze[row][col + 1] != '#' {
        neighbors.push((row, col + 1));
    }
    neighbors
}
fn reconstruct_path(
    parent: &HashMap<(usize, usize), (usize, usize)>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path = vec![];
    let mut current = end;
    path.push(current);
    while current != start {
        match parent.get(&current) {
            Some(&prev) => {
                path.push(prev);
                current = prev;
            }
            None => unreachable!(),
        }
    }
    path.reverse();
    path
}

rawar089

4 months ago

3.60ms

89.35kb

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let max_y = maze[0].len();
    let max_x = maze.len();
    let mut visited = vec![vec![false; max_y]; max_x];
    let mut parent = vec![vec![None; max_y]; max_x];
    let mut queue = VecDeque::new();
    queue.push_back(start);
    visited[start.0][start.1] = true;
    while let Some(pos) = queue.pop_front() {
         if pos == end {
             let mut path = Vec::new();
             let mut pre_pos = Some(pos);
             while let Some(p) = pre_pos  {
                   path.push(p);
                   pre_pos = parent[p.0][p.1];
             }
             path.reverse();
             return path;
         }
         for p in next_positions(pos.0, pos.1, max_x, max_y) {
             if !visited[p.0][p.1] && maze[p.0][p.1] != '#' {
                 queue.push_back(p);
                 visited[p.0][p.1] = true;
                 parent[p.0][p.1] = Some(pos);
             }
         }
    }
    vec![]
}
fn next_positions(x: usize, y: usize, max_x: usize, max_y: usize) -> Vec<(usize, usize)> {
    let mut next_pos = Vec::new();
    if  x < max_x - 1 {
        next_pos.push((x + 1 , y));
    }
    if y <  max_y - 1 {
        next_pos.push((x, y + 1 ));
    }
    if x > 0 {
        next_pos.push((x - 1, y));
    }
    if  y > 0 {
        next_pos.push((x, y - 1));
    }
    next_pos
}

Christopher Nielson

c-nielson

4 months ago

68.97ms

127.63kb

use std::sync::{Arc, Mutex};
use std::thread::{spawn, JoinHandle};/*
S: Start
E: End
.: Path
#: Wall
 */
const START: char = 'S';
const END: char = 'E';
const WALL: char = '#';
const VISITED: char = 'V';
// const PATH: char = '.'; // Assumed that all other characters are valid paths to traverse
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    if maze[start.0][start.1] == END {
        // We reached the end
        vec![(start.0, start.1)]
    } else if maze[start.0][start.1] == WALL || maze[start.0][start.1] == VISITED {
        // We hit a wall or are backtracking
        vec![]
    } else {
        let all_paths: Arc<Mutex<Vec<Vec<(usize, usize)>>>> = Arc::new(Mutex::new(vec![]));
        let mut updated_maze = maze.clone();
        if updated_maze[start.0][start.1] != START {
            updated_maze[start.0][start.1] = VISITED; // Mark current location as visited
        }
        let mut handles: Vec<JoinHandle<()>> = vec![];
        if start.1 < maze[0].len() - 1 {
            // Try right
            let all_paths_clone = Arc::clone(&all_paths);
            let next_maze = Vec::from(updated_maze.clone());
            handles.push(spawn(move || {
                let next_move: (usize, usize) = (start.0, start.1 + 1);
                let result = solve_maze(next_maze, next_move, end);
                if !result.is_empty() {
                    let mut path = vec![(start.0, start.1)];
                    path.extend(result);
                    all_paths_clone.lock().unwrap().push(path);
                }
            }));
        }
        if start.0 < maze.len() - 1 {
            // Try down
            let all_paths_clone = Arc::clone(&all_paths);
            let next_maze = Vec::from(updated_maze.clone());
            handles.push(spawn(move || {
                let next_move: (usize, usize) = (start.0 + 1, start.1);
                let result = solve_maze(next_maze, next_move, end);
                if !result.is_empty() {
                    let mut path = vec![(start.0, start.1)];
                    path.extend(result);
                    all_paths_clone.lock().unwrap().push(path);
                }
            }));
        }
        if start.1 > 0 {
            // Try left
            let all_paths_clone = Arc::clone(&all_paths);
            let next_maze = Vec::from(updated_maze.clone());
            handles.push(spawn(move || {
                let next_move: (usize, usize) = (start.0, start.1 - 1);
                let result = solve_maze(next_maze, next_move, end);
                if !result.is_empty() {
                    let mut path = vec![(start.0, start.1)];
                    path.extend(result);
                    all_paths_clone.lock().unwrap().push(path);
                }
            }));
        }
        if start.0 > 0 {
            // Try up
            let all_paths_clone = Arc::clone(&all_paths);
            let next_maze = Vec::from(updated_maze.clone());
            handles.push(spawn(move || {
                let next_move: (usize, usize) = (start.0 - 1, start.1);
                let result = solve_maze(next_maze, next_move, end);
                if !result.is_empty() {
                    let mut path = vec![(start.0, start.1)];
                    path.extend(result);
                    all_paths_clone.lock().unwrap().push(path);
                }
            }));
        }
        for handle in handles {
            handle.join().unwrap();
        }
        let mut lock = all_paths.lock().unwrap();
        if lock.is_empty() {
            return vec![];
        }
        lock.sort_unstable_by_key(|a| a.len());
        lock[0].clone()
    }
}

Nikita Smirnov

Nismirno

4 months ago

4.41ms

89.30kb

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let height = maze.len();
    let width = maze[0].len();
    let mut s: VecDeque<(usize, usize)> = VecDeque::from([start]);
    let mut visited: Vec<Vec<bool>> = vec![vec![false; width]; height];
    let mut path: Vec<Vec<Option<(usize, usize)>>> = vec![vec![None; width]; height];
    while !s.is_empty() {
        let current_pos = s.pop_front().unwrap();
        let (y, x) = current_pos;
        if current_pos == end {
            let mut result: Vec<(usize, usize)> = vec![];
            let mut current = Some(current_pos);
            while let Some(p) = current {
                result.push(p);
                current = path[p.0][p.1];
            }
            result.reverse();
            return result;
        }
        if !visited[y][x] {
            visited[y][x] = true;
            let neighbors = find_valid_neighbors(&maze, current_pos);
            for neighbour in neighbors {
                let (next_y, next_x) = neighbour;
                if !visited[next_y][next_x] {
                    s.push_back(neighbour);
                    path[next_y][next_x] = Some(current_pos);
                }
            }
        }
    }
    vec![]
}
fn find_valid_neighbors(maze: &[Vec<char>], pos: (usize, usize)) -> Vec<(usize, usize)> {
    let mut neighbors = vec![];
    let directions = vec![
        Direction::Up,
        Direction::Down,
        Direction::Left,
        Direction::Right,
    ];
    let height = maze.len() - 1;
    let width = maze[0].len() - 1;
    for dir in directions {
        if let Some(pos) = dir.move_from(pos, width, height) {
            let (y, x) = pos;
            match maze[y][x] {
                '.' | 'E' => neighbors.push(pos),
                _ => {}
            }
        };
    }
    neighbors
}
#[derive(Debug)]
enum Direction {
    Up,
    Down,
    Left,
    Right,
}
impl Direction {
    fn move_from(
        &self,
        point: (usize, usize),
        width: usize,
        height: usize,
    ) -> Option<(usize, usize)> {
        let (y, x) = point;
        match self {
            Direction::Up => match y == 0 {
                true => None,
                false => Some((y.wrapping_sub(1), x)),
            },
            Direction::Down => match y == height {
                true => None,
                false => Some((y.wrapping_add(1), x)),
            },
            Direction::Left => match x == 0 {
                true => None,
                false => Some((y, x.wrapping_sub(1))),
            },
            Direction::Right => match x == width {
                true => None,
                false => Some((y, x.wrapping_add(1))),
            },
        }
    }
}

Florian Gaudin-Delrieu

FlorianGD

5 months ago

4.81ms

90.90kb

use std::collections::HashSet;
type Pos = (isize, isize);
type Grid = HashSet<Pos>;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let grid = build_grid(maze);
    let start = (start.0 as isize, start.1 as isize);
    let end = (end.0 as isize, end.1 as isize);
    match solve_recursive(start, &grid, &Vec::new(), &end) {
        Some(p) => p.iter().map(|(x, y)| (*x as usize, *y as usize)).collect(),
        None => Vec::new()
    }
}
fn solve_recursive(pos: Pos, grid: &Grid, path: &Vec<Pos>, end: &Pos) -> Option<Vec<Pos>> {
    let mut path = path.clone();
    path.push(pos);
    if pos == *end {
        return Some(path.to_owned());
    }
    let nexts = successors(pos, grid);
    nexts
        .into_iter()
        .filter(|p| !path.contains(p))
        .filter_map(|p| solve_recursive(p, grid, &path, end))
        .next()
}
fn build_grid(maze: Vec<Vec<char>>) -> Grid {
    let mut grid: Grid = Grid::default();
    for (i, v) in maze.iter().enumerate() {
        for (j, c) in v.iter().enumerate() {
            match c {
                '.' | 'S' | 'E' => grid.insert((i as isize, j as isize)),
                _ => continue,
            };
        }
    }
    grid
}
fn successors((x, y): Pos, grid: &Grid) -> Vec<Pos> {
    [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]
        .iter()
        .filter(|p| grid.contains(p))
        .copied()
        .collect()
}

dawwestk

5 months ago

3.45ms

89.35kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    use std::collections::VecDeque;
    let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)];
    let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
    let mut visited = vec![vec![false; maze[0].len()]; maze.len()];
    let mut path = vec![vec![None; maze[0].len()]; maze.len()];
    queue.push_back(start);
    visited[start.0][start.1] = true;
    while let Some((x, y)) = queue.pop_front() {
        if (x, y) == end {
            let mut p = vec![];
            let mut current = Some((x, y));
            while let Some(c) = current {
                p.push(c);
                current = path[c.0][c.1];
            }
            p.reverse();
            return p;
        }
        for &(dx, dy) in &directions {
            let nx = x.wrapping_add(dx as usize);
            let ny = y.wrapping_add(dy as usize);
            if nx < maze.len() && ny < maze[0].len() && maze[nx][ny] != '#' && !visited[nx][ny] {
                queue.push_back((nx, ny));
                visited[nx][ny] = true;
                path[nx][ny] = Some((x, y));
            }
        }
    }
    vec![]
}

PangoSea

kapaseker

5 months ago

5.23ms

89.35kb


use std::collections::VecDeque;
pub fn neighbors(pos: (usize, usize), max_x: usize, max_y: usize) -> Vec<(usize, usize)> {
    let (x, y) = pos;
    let mut neighbors = Vec::new();
    if x > 0 {
        neighbors.push((x - 1, y));
    }
    if y > 0 {
        neighbors.push((x, y - 1));
    }
    if x < max_x - 1 {
        neighbors.push((x + 1, y));
    }
    if y < max_y - 1 {
        neighbors.push((x, y + 1));
    }
    neighbors
}
pub fn solve_maze(maze: Vec<Vec<char>>, start: (usize, usize), end: (usize, usize)) -> Vec<(usize, usize)> {
    let mut queue = VecDeque::new();
    let mut visited = vec![vec![false; maze[0].len()]; maze.len()];
    let mut parent = vec![vec![None; maze[0].len()]; maze.len()];
    queue.push_back(start);
    visited[start.0][start.1] = true;
    while let Some(current) = queue.pop_front() {
        if current == end {
            let mut path = Vec::new();
            let mut step = Some(current);
            while let Some(pos) = step {
                path.push(pos);
                step = parent[pos.0][pos.1];
            }
            path.reverse();
            return path;
        }
        for neighbor in neighbors(current, maze.len(), maze[0].len()) {
            if !visited[neighbor.0][neighbor.1] && maze[neighbor.0][neighbor.1] != '#' {
                queue.push_back(neighbor);
                visited[neighbor.0][neighbor.1] = true;
                parent[neighbor.0][neighbor.1] = Some(current);
            }
        }
    }
    vec![]
}

Ahmet Özcan

ahmetoozcan

5 months ago

3.94ms

89.11kb

use std::collections::{HashMap, VecDeque};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let rows = maze.len();
    let cols = maze[0].len();
    let mut queue = VecDeque::new();
    queue.push_back(start);
    let mut visited = HashMap::new();
    visited.insert(start, start);
    while let Some(current) = queue.pop_front() {
        if current == end {
            return reconstruct_path(&visited, start, end);
        }
        for next in get_valid_neighbors(current, &maze, rows, cols) {
            if !visited.contains_key(&next) {
                visited.insert(next, current);
                queue.push_back(next);
            }
        }
    }
    vec![]
}
fn get_valid_neighbors(
    pos: (usize, usize),
    maze: &Vec<Vec<char>>,
    rows: usize,
    cols: usize,
) -> Vec<(usize, usize)> {
    let (row, col) = pos;
    let mut neighbors = Vec::new();
    let directions = [
        (0, 1),  // right
        (1, 0),  // down
        (0, -1), // left
        (-1, 0), // up
    ];
    for (dx, dy) in directions {
        let new_row = row as i32 + dx;
        let new_col = col as i32 + dy;
        if new_row >= 0 && new_row < rows as i32 && new_col >= 0 && new_col < cols as i32 {
            let new_row = new_row as usize;
            let new_col = new_col as usize;
            if maze[new_row][new_col] != '#' {
                neighbors.push((new_row, new_col));
            }
        }
    }
    neighbors
}
fn reconstruct_path(
    visited: &HashMap<(usize, usize), (usize, usize)>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path = Vec::new();
    let mut current = end;
    while current != start {
        path.push(current);
        current = *visited.get(&current).unwrap();
    }
    path.push(start);
    path.reverse();
    path
}

Lauri Sarap

LauriSarap

5 months ago

3.72ms

94.07kb

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let rows = maze.len();
    let cols = maze[0].len();
    let mut visited: Vec<Vec<bool>> = vec![vec![false; cols]; rows];
    let mut previous: Vec<Vec<Option<(usize, usize)>>> = vec![vec![None; cols]; rows];
    let mut queue = VecDeque::new();
    queue.push_back(start);
    visited[start.0][start.1] = true;
    let directions: Vec<(i32, i32)> = vec![(0, 1), (0, -1), (1, 0), (-1, 0)];
    while let Some((x, y)) = queue.pop_front() {
        if (x, y) == end {
            println!("Reached the end!");
            println!("Visited: {:?}", visited);
            println!("Previous: {:?}", previous);
            let mut path = vec![];
            let mut current = Some((x, y));
            while let Some(pos) = current {
                println!("Adding to path: {:?}", pos);
                path.push(pos);
                current = previous[pos.0][pos.1];
            }
            path.reverse();
            return path;
        }
        for (dx, dy) in &directions {
            let nx = (x as i32 + dx) as usize;
            let ny = (y as i32 + dy) as usize;
            if nx < rows && ny < cols && maze[nx][ny] != '#' && !visited[nx][ny] {
                queue.push_back((nx, ny));
                visited[nx][ny] = true;
                println!("Just visited: {:?}", (nx, ny));
                previous[nx][ny] = Some((x, y));
            }
        }
    }
    vec![]
}

Joe Schneider

josschne

5 months ago

3.66ms

89.35kb

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let height = maze.len();
    let width = maze[0].len();
    
    // Initialize our tracking structures
    let mut visited = vec![vec![false; width]; height];
    let mut parent = vec![vec![None; width]; height];
    let mut queue = VecDeque::new();
    
    // Start BFS from start position
    queue.push_back(start);
    visited[start.0][start.1] = true;
    
    // These will be our possible moves: up, right, down, left
    let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)];
    while let Some(current) = queue.pop_front() {
        if current == end {
            return reconstruct_path(&parent, start, end);
        }
        // Check each direction
        for (dx, dy) in directions {
            // Convert current position for safe arithmetic
            let cur_row = current.0 as i32;
            let cur_col = current.1 as i32;
            
            // Calculate new position
            let new_row = cur_row + dx;
            let new_col = cur_col + dy;
            
            // Validate new position
            if new_row >= 0 && new_row < height as i32 && 
               new_col >= 0 && new_col < width as i32 {
                
                let new_pos = (new_row as usize, new_col as usize);
                
                // Check if this is a valid unvisited path
                if !visited[new_pos.0][new_pos.1] && maze[new_pos.0][new_pos.1] != '#' {
                    visited[new_pos.0][new_pos.1] = true;
                    parent[new_pos.0][new_pos.1] = Some(current);
                    queue.push_back(new_pos);
                }
            }
        }
    }
    
    // No path found
    vec![]
}
fn reconstruct_path(
    parent: &Vec<Vec<Option<(usize, usize)>>>,
    start: (usize, usize),
    end: (usize, usize)
) -> Vec<(usize, usize)> {
    let mut path = Vec::new();
    let mut current = end;
    
    // Work backwards from end to start
    path.push(current);
    
    while current != start {
        match parent[current.0][current.1] {
            Some(prev) => {
                path.push(prev);
                current = prev;
            }
            None => return vec![] // No path exists
        }
    }
    
    // Reverse to get path from start to end
    path.reverse();
    path
}

Võ Thanh Bình

pynhpo

5 months ago

3.81ms

89.35kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    use std::collections::VecDeque;
    let mut queue = VecDeque::new();
    queue.push_back(start);
    let num_of_rows = maze.len();
    let num_of_cols = maze[0].len();
    let mut visited = vec![vec![false; num_of_cols]; num_of_rows];
    let mut parents = vec![vec![None; num_of_cols]; num_of_rows];
    let directions = [(0, 1), (1, 0), (0, usize::MAX), (usize::MAX, 0)];
    while let Some((y, x)) = queue.pop_front() {
        if (y, x) == end {
            let mut path = vec![(y, x)];
            let mut current = (y, x);
            while let Some(parent) = parents[current.0][current.1] {
                path.push(parent);
                current = parent;
            }
            path.reverse();
            return path;
        }
        if visited[y][x] {
            continue;
        }
        visited[y][x] = true;
        for &direction in &directions {
            let next_y = y.wrapping_add(direction.0);
            let next_x = x.wrapping_add(direction.1);
            if next_y < num_of_rows && next_x < num_of_cols && !visited[next_y][next_x] && maze[next_y][next_x] != '#' {
                queue.push_back((next_y, next_x));
                parents[next_y][next_x] = Some((y, x));
            }
        }
    }
    vec![]
}

Denis SOURON

Brack0

5 months ago

3.52ms

88.80kb

use std::collections::VecDeque;
fn is_valid_cell(maze: &[Vec<char>], cell: (usize, usize)) -> bool {
    cell.0 < maze.len() && cell.1 < maze.first().map_or(0, |row| row.len())
}
fn is_a_wall(maze: &[Vec<char>], cell: (usize, usize)) -> bool {
    maze[cell.0][cell.1] == '#'
}
fn get_adjacent_cells(cell: (usize, usize)) -> Vec<(usize, usize)> {
    vec![
        (cell.0.wrapping_sub(1), cell.1),
        (cell.0 + 1, cell.1),
        (cell.0, cell.1.wrapping_sub(1)),
        (cell.0, cell.1 + 1),
    ]
}
fn build_path(maze: &[Vec<char>], start: (usize, usize), end: (usize, usize)) -> Vec<Vec<usize>> {
    let mut path: Vec<Vec<usize>> =
        vec![vec![0; maze.first().map_or(0, |row| row.len())]; maze.len()];
    let mut visited: Vec<Vec<bool>> =
        vec![vec![false; maze.first().map_or(0, |row| row.len())]; maze.len()];
    let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
    visited[start.0][start.1] = true;
    path[start.0][start.1] = 1;
    queue.push_back(start);
    'outer: while !queue.is_empty() {
        let cell = queue.pop_front().unwrap();
        for (x, y) in get_adjacent_cells(cell)
            .into_iter()
            .filter(|&c| is_valid_cell(maze, c))
            .filter(|&c| !is_a_wall(maze, c))
        {
            if !visited[x][y] {
                visited[x][y] = true;
                queue.push_back((x, y));
                path[x][y] = path[cell.0][cell.1] + 1;
                if (x, y) == end {
                    break 'outer;
                }
            }
        }
    }
    path
}
fn find_shortest_path(
    maze: &[Vec<char>],
    start: (usize, usize),
    end: (usize, usize),
    path: &[Vec<usize>],
) -> Vec<(usize, usize)> {
    let mut coords = (end.0, end.1);
    let mut shortest_path = vec![coords];
    while coords != start {
        for (x, y) in get_adjacent_cells(coords)
            .into_iter()
            .filter(|&c| is_valid_cell(maze, c))
        {
            if path[x][y] == path[coords.0][coords.1] - 1 {
                coords = (x, y);
                break;
            }
        }
        shortest_path.insert(0, coords);
    }
    shortest_path
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let path = build_path(&maze, start, end);
    if path[end.0][end.1] == 0 {
        return vec![];
    }
    find_shortest_path(&maze, start, end, &path)
}

Caio César

caiocdcs

5 months ago

3.98ms

89.35kb

use std::collections::VecDeque;
const UP: (isize, isize) = (-1, 0);
const DOWN: (isize, isize) = (1, 0);
const LEFT: (isize, isize) = (0, -1);
const RIGHT: (isize, isize) = (0, 1);
struct Maze {
    grid: Vec<Vec<char>>,
    visited: Vec<Vec<bool>>,
    parent: Vec<Vec<Option<(usize, usize)>>>,
}
impl Maze {
    fn new(grid: Vec<Vec<char>>) -> Self {
        let rows = grid.len();
        let cols = grid[0].len();
        Maze {
            grid,
            visited: vec![vec![false; cols]; rows],
            parent: vec![vec![None; cols]; rows],
        }
    }
    fn rows(&self) -> usize {
        self.grid.len()
    }
    fn cols(&self) -> usize {
        self.grid[0].len()
    }
    fn is_valid(&self, x: usize, y: usize) -> bool {
        x < self.rows()
        && y < self.cols()
        && self.grid[x][y] != '#'
        && !self.visited[x][y]
    }
    fn backtrack_from(&self, x: usize, y: usize) -> Vec<(usize, usize)> {
        let mut path = vec![(x, y)];
        let mut current = (x, y);
    
        while let Some(previous) = self.parent[current.0][current.1] {
            path.push(previous);
            current = previous;
        }
        path.reverse();
        path
    }
    fn solve(&mut self, start: (usize, usize), end: (usize, usize)) -> Result<Vec<(usize, usize)>, ()> {
        let mut queue = VecDeque::new();
        queue.push_back(start);
        self.visited[start.0][start.1] = true;
        while let Some((x, y)) = queue.pop_front() {
            if (x, y) == end {
                return Ok(self.backtrack_from(x, y));
            }
            for dir in [UP, DOWN, LEFT, RIGHT] {
                let new_x = (x as isize + dir.0) as usize;
                let new_y = (y as isize + dir.1) as usize;
                if self.is_valid(new_x, new_y) {
                    self.visited[new_x][new_y] = true;
                    self.parent[new_x][new_y] = Some((x, y));
                    queue.push_back((new_x, new_y));
                }
            }
        }
        Err(())
    }
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    
    let mut maze = Maze::new(maze);
    if let Ok(result) = maze.solve(start, end) {
        return result;
    }
    Vec::new()
}

hubbardip

5 months ago

4.59ms

90.49kb

use std::collections::HashSet;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut p = solve_maze_helper(&maze, start, end, &HashSet::new());
    p.reverse();
    p
}
fn available(maze: &Vec<Vec<char>>, pos: (usize, usize), used: &HashSet<(usize, usize)>) -> bool {
    //returns true if the given pos is open in the maze and hasn't been used
    (pos.0 < maze.len())
        && (pos.1 < maze[pos.0].len())
        && (maze[pos.0][pos.1] != '#')
        && !used.contains(&pos)
}
fn neighbors(
    maze: &Vec<Vec<char>>,
    pos: (usize, usize),
    used: &HashSet<(usize, usize)>,
) -> Vec<(usize, usize)> {
    //returns available moves from pos
    let pos_neighbors: Vec<(usize, usize)>;
    if (pos.0 == 0) & (pos.1 == 0) {
        pos_neighbors = vec![(pos.0 + 1, pos.1), (pos.0, pos.1 + 1)];
    } else if pos.0 == 0 {
        pos_neighbors = vec![(pos.0 + 1, pos.1), (pos.0, pos.1 - 1), (pos.0, pos.1 + 1)];
    } else if pos.1 == 0 {
        pos_neighbors = vec![(pos.0 - 1, pos.1), (pos.0 + 1, pos.1), (pos.0, pos.1 + 1)];
    } else {
        pos_neighbors = vec![
            (pos.0 - 1, pos.1),
            (pos.0 + 1, pos.1),
            (pos.0, pos.1 - 1),
            (pos.0, pos.1 + 1),
        ]
    }
    pos_neighbors
        .into_iter()
        .filter(|&x| available(maze, x, used))
        .collect()
}
fn solve_maze_helper(
    maze: &Vec<Vec<char>>,
    pos: (usize, usize),
    end: (usize, usize),
    used: &HashSet<(usize, usize)>,
) -> Vec<(usize, usize)> {
    //returns a path from end to pos, without using anything in used, if such a path exists
    let mut newused = used.clone();
    newused.insert(pos);
    let mut s_path = vec![];
    let mut s_len = 1e10 as usize;
    for p in neighbors(maze, pos, used) {
        if p == end {
            s_path = vec![p];
            break;
        }
        let path = solve_maze_helper(maze, p, end, &newused);
        if path.len() == 0 {
            //no path exists
            continue;
        }
        if path.len() < s_len {
            s_len = path.len();
            s_path = path;
        }
    }
    if s_path.len() >= 1 {
        //if len is 0, there is no path
        s_path.push(pos);
    }
    s_path
}

viky

vikyw89

5 months ago

3.99ms

91.93kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    return get_shortest_path(&maze, start, end, vec![(start.0, start.1)]);
}
fn get_shortest_path(
    maze: &Vec<Vec<char>>,
    current_pos: (usize, usize),
    end: (usize, usize),
    traveled_path: Vec<(usize, usize)>,
) -> Vec<(usize, usize)> {
    println!("current_pos: {:?}", current_pos);
    // Your code here
    // base case
    // if end
    if current_pos == end {
        return traveled_path;
    }
    // recursive case
    // get all possible moves
    let possible_moves = get_possible_moves(&maze, current_pos);
    let unique_next_moves: Vec<(usize, usize)> = possible_moves
        .into_iter()
        .filter(|next_move| !traveled_path.contains(&next_move))
        .collect();
    // for each move, get the shortest path
    let mut shortest_path = vec![];
    for next_move in unique_next_moves {
        let mut traveled_path_copy = traveled_path.clone();
        traveled_path_copy.push(next_move);
        let new_path = get_shortest_path(maze, next_move, end, traveled_path_copy);
        // if no path, continue
        if new_path.len() == 0 {
            continue;
        }
        // if no shortest path, set shortest path
        if shortest_path.len() == 0 {
            shortest_path = new_path;
            continue;
        }
        if new_path.len() < shortest_path.len() {
            shortest_path = new_path;
        }
    }
    return shortest_path;
}
fn get_possible_moves(maze: &Vec<Vec<char>>, current_pos: (usize, usize)) -> Vec<(usize, usize)> {
    let y_pos = current_pos.0;
    let x_pos = current_pos.1;
    // get all next moves
    let mut next_moves = vec![];
    // up
    if y_pos > 0 && maze[y_pos - 1][x_pos] != '#' {
        next_moves.push((y_pos - 1, x_pos));
    }
    // down
    if y_pos < maze.len() - 1 && maze[y_pos + 1][x_pos] != '#' {
        next_moves.push((y_pos + 1, x_pos));
    }
    // left
    if x_pos > 0 && maze[y_pos][x_pos - 1] != '#' {
        next_moves.push((y_pos, x_pos - 1));
    }
    // right
    if x_pos < maze[0].len() - 1 && maze[y_pos][x_pos + 1] != '#' {
        next_moves.push((y_pos, x_pos + 1));
    }
    return next_moves;
}

Giuliano

GiulianoCTRL

5 months ago

4.08ms

89.35kb

use std::collections::VecDeque;
const UP: (isize, isize) = (-1, 0);
const DOWN: (isize, isize) = (1, 0);
const LEFT: (isize, isize) = (0, -1);
const RIGHT: (isize, isize) = (0, 1);
struct Maze {
    grid: Vec<Vec<char>>,
    visited: Vec<Vec<bool>>,
    parent: Vec<Vec<Option<(usize, usize)>>>,
}
impl Maze {
    fn new(grid: Vec<Vec<char>>) -> Self {
        let rows = grid.len();
        let cols = grid[0].len();
        Maze {
            grid,
            visited: vec![vec![false; cols]; rows],
            parent: vec![vec![None; cols]; rows],
        }
    }
    fn rows(&self) -> usize {
        self.grid.len()
    }
    fn cols(&self) -> usize {
        self.grid[0].len()
    }
    fn is_valid(&self, x: usize, y: usize) -> bool {
        x < self.rows()
        && y < self.cols()
        && self.grid[x][y] != '#'
        && !self.visited[x][y]
    }
    fn backtrack_from(&self, x: usize, y: usize) -> Vec<(usize, usize)> {
        let mut path = vec![(x, y)];
        let mut current = (x, y);
    
        while let Some(previous) = self.parent[current.0][current.1] {
            path.push(previous);
            current = previous;
        }
        path.reverse();
        path
    }
    fn solve(&mut self, start: (usize, usize), end: (usize, usize)) -> Result<Vec<(usize, usize)>, ()> {
        let mut queue = VecDeque::new();
        queue.push_back(start);
        self.visited[start.0][start.1] = true;
        while let Some((x, y)) = queue.pop_front() {
            if (x, y) == end {
                return Ok(self.backtrack_from(x, y));
            }
            for dir in [UP, DOWN, LEFT, RIGHT] {
                let new_x = (x as isize + dir.0) as usize;
                let new_y = (y as isize + dir.1) as usize;
                if self.is_valid(new_x, new_y) {
                    self.visited[new_x][new_y] = true;
                    self.parent[new_x][new_y] = Some((x, y));
                    queue.push_back((new_x, new_y));
                }
            }
        }
        Err(())
    }
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    
    let mut maze = Maze::new(maze);
    if let Ok(result) = maze.solve(start, end) {
        return result;
    }
    Vec::new()
}

Esteban Soba

XtebanUy

5 months ago

3.53ms

88.93kb

use std::result;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    if start == end
    {
        return vec![start];
    }
    let mut routes = vec![vec![start]];
    let mut routes_len = 1;
    let max_x = maze.len() - 1;
    let max_y = maze[0].len() - 1;
    
    while !routes.is_empty() {
        
        let mut new_routes = vec![];
        
        for route in &routes  {
            
            let (last_node_x, lats_node_y) = route[routes_len -1];
            for (x, y) in get_movements((last_node_x, lats_node_y), max_x, max_y) {
 
                let maze_pos_value = maze[x][y];
                if end == (x, y)
                {
                    let mut result : Vec<(usize, usize)> = route.iter().cloned().collect();
                    result.push((x,y));
                    return result;
                }
                if maze_pos_value != '#' && !route.contains(&(x,y))
                {
                    let mut new_route : Vec<(usize, usize)> = route.iter().cloned().collect();
                    new_route.push((x,y));
                    new_routes.push(new_route);
                }
            }
        }
        routes.clear();
        for route in new_routes  {
            routes.push(route);
        }
        routes_len += 1;
    }
    
    vec![]
}
pub fn get_movements(pos: (usize, usize), max_x: usize, max_y: usize) -> Vec<(usize, usize)>
{
    let mut movements = vec![];
    let (x, y) = pos;
    
    if x > 0
    {
        movements.push((x - 1, y));
    }
    if x < max_x {
        movements.push((x + 1, y));
    }
    if y > 0 {
        movements.push((x , y - 1));
    }
    if y < max_y {
        movements.push((x , y + 1));
    }
    movements
}

mgreve

5 months ago

3.96ms

88.98kb

struct ElemWithDistance {
    x: i32,
    y: i32,
    d: u32,
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Owns the nodes in the graph
    let mut deque: std::collections::VecDeque<ElemWithDistance> = std::collections::VecDeque::new();
    let mut coords_seen: std::collections::HashSet<(i32, i32)> = std::collections::HashSet::new();
    let mut pred: std::collections::HashMap<(i32,i32), Option<(i32, i32)> > = std::collections::HashMap::new();
    let mut ret: Vec<(usize, usize)> = Vec::new();
    let start_element = ElemWithDistance{x: start.0 as i32, y: start.1 as i32, d: 0};
    pred.insert((start.0 as i32, start.1 as i32), None);
    coords_seen.insert((start.0 as i32, start.1 as i32));
    deque.push_back(start_element);
    while deque.len() > 0 {
        let cur_elem = deque.pop_front().unwrap();
        if cur_elem.x == end.0 as i32 && cur_elem.y == end.1 as i32 {
            let mut p = Some((cur_elem.x, cur_elem.y));
            while !p.is_none() {
                let elem = p.unwrap();
                ret.push((elem.0 as usize, elem.1 as usize));
                p = pred.get(&(elem.0, elem.1)).unwrap().clone()
            }
            ret.reverse();
            return ret;
        }
        const dir: [i32; 4] = [0,1,-1,1];
        for dx in dir {
            for dy in dir {
                if dx.abs() + dy.abs() != 1 {
                    continue
                }
                let nx = cur_elem.x as i32 + dx;
                let ny = cur_elem.y as i32 + dy;
                if nx < 0 || nx as usize >= maze.len() {
                    continue;
                }
                if ny < 0 || ny as usize >= maze[nx as usize].len() {
                    continue;
                }
                if maze[nx as usize][ny as usize] == '#' {
                    continue;
                }
                if coords_seen.contains(&(nx, ny)) {
                    continue;
                }
                let next_elem = ElemWithDistance{ x: nx, y: ny, d: cur_elem.d + 1 };
                pred.insert((nx,ny), Some((cur_elem.x, cur_elem.y)));
                deque.push_back(next_elem);
                coords_seen.insert((nx,ny));
            }
        }
    }
    ret
}

Jim Lawton

jimlawton

5 months ago

7.02ms

88.91kb

use std::collections::VecDeque;
type Point = (usize, usize);
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: Point,
    end: Point,
) -> Vec<Point> {
    let height = maze.len();
    let width = maze[0].len(); // Assuming all rows are the same length.
    let (start_x, start_y) = start;
    let (end_x, end_y) = end;
    
    if start_x >= height || start_y >= width || end_x >= height || end_y >= width {
        println!("Start or end is outside the maze!");
        return vec![];
    }
    if maze[start_x][start_y] != 'S' || maze[end_x][end_y] != 'E' {
        println!("Invalid start or end position!");
        return vec![];
    }
    let mut queue = VecDeque::<Vec<Point>>::new();
    queue.push_back(vec![start]);
    while !queue.is_empty() {
        let path = queue.pop_front().unwrap();
        let (x, y) = path[path.len() - 1];
        if (x, y) == end {
            // Found solution.
            return path;
        }
        let directions: Vec<(i32, i32)> = vec![(1, 0), (0, 1), (-1, 0), (0, -1)];
        for (dx, dy) in directions {
            let (next_x, next_y) = (x as i32 + dx, y as i32 + dy);
            if next_x < 0 || next_y < 0 {
                continue; // Outside the maze.
            }
            let (next_x, next_y) = (next_x as usize, next_y as usize);
            if next_x >= height || next_y >= width {
                continue; // Outside the maze.
            }
            if maze[next_x][next_y] != '#' && !path.contains(&(next_x, next_y)) {
                let mut new_path = path.clone();
                new_path.append(&mut vec![(next_x, next_y)]);
                queue.push_back(new_path);
            }
        }
    }
    Vec::<Point>::new()
}

Dagur Arinbjörn Daníelsson

gardyna

5 months ago

3.68ms

88.83kb


use std::{collections::{HashSet, VecDeque}, path::Display};
use std::fmt;
//  --> y
//  | ['S', '.', '#', '#', '#'], [0][*] [x][y]
//  x ['#', '.', '#', '.', '.'], [1][*]
//    ['#', '.', '.', '.', '#'], [2][*]
//    ['#', '#', '#', '.', '#'], [3][*]
//    ['#', '#', '#', 'E', '#']
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
struct Point {
    x: i32,
    y: i32
}
// Implement Display trait for Point
impl fmt::Display for Point {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "({}, {})", self.x, self.y)
    }
}
impl Point {
    fn neighbor(&self) -> Vec<Point>{
        vec![
            Point{x: self.x,     y: self.y + 1}, // right
            Point{x: self.x + 1, y: self.y},     // down
            Point{x: self.x,     y: self.y - 1}, // left
            Point{x: self.x - 1, y: self.y}      // up
        ]
    }    
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    if maze.is_empty() || maze[0].is_empty() {
        return vec![];
    }
    let rows = maze.len() as i32;
    let cols = maze[0].len() as i32;
    let start = Point{x: start.0 as i32, y: start.1 as i32};
    let end = Point{x: end.0 as i32, y: end.1 as i32};
    let mut visited:HashSet<Point> = HashSet::new();
    let mut queue: VecDeque<(Point,Vec<Point>)> = VecDeque::new();
    visited.insert(start);
    queue.push_back((start, vec![start]));
    while let Some((current, path)) = queue.pop_front() {
        // check goal reach condition
        if current == end {
            return path.into_iter()
                    .map(|p|(p.x as usize, p.y as usize))
                    .collect();
        }
        
        // println!("current: {}, neighbor: {:?}",current, current.neighbor());
        for next in current.neighbor(){
            // skip out of scope 
            if next.x < 0 || next.x >= rows || next.y < 0 || next.y >= cols {
                continue;
            }
            // skip wall
            if maze[next.x as usize][next.y as usize] == '#' {
                continue;
            }
            // skip already visited
            if visited.contains(&next) {
                continue;
            }
            let mut new_path = path.clone();
            new_path.push(next);
            visited.insert(next);
            queue.push_back((next, new_path));
        }
    }
    vec![]
}

sorawit112

5 months ago

3.98ms

88.83kb

use std::{collections::{HashSet, VecDeque}, path::Display};
use std::fmt;
//  --> y
//  | ['S', '.', '#', '#', '#'], [0][*] [x][y]
//  x ['#', '.', '#', '.', '.'], [1][*]
//    ['#', '.', '.', '.', '#'], [2][*]
//    ['#', '#', '#', '.', '#'], [3][*]
//    ['#', '#', '#', 'E', '#']
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
struct Point {
    x: i32,
    y: i32
}
// Implement Display trait for Point
impl fmt::Display for Point {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "({}, {})", self.x, self.y)
    }
}
impl Point {
    fn neighbor(&self) -> Vec<Point>{
        vec![
            Point{x: self.x,     y: self.y + 1}, // right
            Point{x: self.x + 1, y: self.y},     // down
            Point{x: self.x,     y: self.y - 1}, // left
            Point{x: self.x - 1, y: self.y}      // up
        ]
    }    
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    if maze.is_empty() || maze[0].is_empty() {
        return vec![];
    }
    let rows = maze.len() as i32;
    let cols = maze[0].len() as i32;
    let start = Point{x: start.0 as i32, y: start.1 as i32};
    let end = Point{x: end.0 as i32, y: end.1 as i32};
    let mut visited:HashSet<Point> = HashSet::new();
    let mut queue: VecDeque<(Point,Vec<Point>)> = VecDeque::new();
    visited.insert(start);
    queue.push_back((start, vec![start]));
    while let Some((current, path)) = queue.pop_front() {
        // check goal reach condition
        if current == end {
            return path.into_iter()
                    .map(|p|(p.x as usize, p.y as usize))
                    .collect();
        }
        
        // println!("current: {}, neighbor: {:?}",current, current.neighbor());
        for next in current.neighbor(){
            // skip out of scope 
            if next.x < 0 || next.x >= rows || next.y < 0 || next.y >= cols {
                continue;
            }
            // skip wall
            if maze[next.x as usize][next.y as usize] == '#' {
                continue;
            }
            // skip already visited
            if visited.contains(&next) {
                continue;
            }
            let mut new_path = path.clone();
            new_path.push(next);
            visited.insert(next);
            queue.push_back((next, new_path));
        }
    }
    vec![]
}

Shoma Kobayashi

kobapi28

5 months ago

3.45ms

89.15kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let mut result = vec![vec![start]];
    loop {
        let old_result = result.clone();
        result = result
            .iter()
            .flat_map(|path| {
                [(1, 0), (-1, 0), (0, 1), (0, -1)]
                    .into_iter()
                    .filter_map(|(drow, dcol)| {
                        let (r, c) = path.iter().last()?;
                        let (r2, c2) = (r.wrapping_add_signed(drow), c.wrapping_add_signed(dcol));
                        let next = maze.get(r2).and_then(|row| row.get(c2))?;
                        if matches!(next, 'E' | '.') && !path.contains(&(r2, c2)) {
                            let mut new_path = path.clone();
                            new_path.push((r2, c2));
                            Some(new_path)
                        } else {
                            None
                        }
                    })
            })
            .collect();
        if result
            .iter()
            .any(|path| path.last().is_some_and(|l| *l == end))
            || result == old_result
        {
            break result
                .into_iter()
                .find(|path| path.last() == Some(&end))
                .unwrap_or(vec![]);
        }
    }
}

Len Remmerswaal

LenRemmerswaal

5 months ago

4.51ms

106.26kb

use std::collections::VecDeque;
use std::collections::HashSet;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    print_map(&maze);
    // Solve maze
    let mut states = VecDeque::new();    // Holds the position to investigate
    let mut visited = HashSet::new();   // Holds the positions visited in the past
    let szx = maze.len();
    let szy = maze[0].len();
    states.push_back(State { pos: start, path: vec![]});
    while !states.is_empty() {
        let current = states.pop_front().unwrap();
        println!("Current: {current:?}");
        if current.pos == end {
            let mut endpath = current.path.clone();
            endpath.push(end);
            return endpath;
        }
        if visited.contains(&current.pos) {
            continue;   // Have been here before. Forget this avenue
        }
        visited.insert(current.pos);
        for delta in [(-1,0), (0,1), (1,0), (0, -1)] {
            print!("Trying ({},{})", delta.0, delta.1);
            if let Some((x, y)) = new_pos(current.pos, delta, (szx, szy)) {
                println!(" ==> testing ({},{})", x, y );
                if maze[x][y] == '#' {
                    continue; // There is a wall here
                }
                let mut new_state = current.clone();  
                new_state.path.push(current.pos);
                new_state.pos = (x, y);
                states.push_back(new_state);
            } else {
                println!(" ==> No successor")
            }
        }
    }
    vec![]
}
#[derive(PartialEq, Eq, Hash, Clone, Debug)]
struct State {
    pos: (usize, usize),            // Position to investigate
    path: Vec<(usize, usize)>,      // Path to get to this point, excluding the point
}
fn new_pos(pos: (usize, usize), delta: (i8, i8), size: (usize, usize)) -> Option<(usize, usize)> {
    if (pos.0 == 0          && delta.0 < 0) ||
       (pos.0 == size.0 - 1 && delta.0 > 0) ||  
       (pos.1 ==  0         && delta.1 < 0) ||  
       (pos.1 == size.1 - 1 && delta.1 > 0) {
        None 
    }  else {
        let p0 = if delta.0 < 0 { pos.0 - 1 } else { pos.0 + delta.0 as usize };
        let p1 = if delta.1 < 0 { pos.1 - 1 } else { pos.1 + delta.1 as usize };
        Some((p0, p1))
    }
}
fn print_map(maze: &Vec<Vec<char>>) {
    for line in maze {
        let linestr: String = line.iter().collect();
        println!("{linestr}");   
    }
}

Javier Garcia

javigar322

5 months ago

4.51ms

89.29kb

use std::collections::{HashMap, HashSet, VecDeque};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
      if maze.len() == 0 || maze[0].len() == 0 {
    return Vec::new()
  }
  let n = maze.len() as i32;
  let m = maze[0].len() as i32;
  println!("n={} m={}", n, m);
  let dirs: Vec<(i32, i32)> = vec![(0, 1), (0, -1), (1, 0), (-1, 0)];
  let mut pre = HashMap::new();
  pre.insert(start, (100000, 100000));
  let mut q = VecDeque::new();
  q.push_back(start);
  while q.len() > 0 {
    let (i, j) = q.pop_front().unwrap();
    // println!("Doing {} {}", i, j);
    for (di, dj) in &dirs {
      let (ni, nj) = (i as i32 + di, j as i32 + dj);
      // println!("Neighbor {} {}", ni, nj);
      if 0 <= ni && ni < n && 0 <= nj && nj < m && maze[ni as usize][nj as usize] != '#' && !pre.contains_key(&(ni as usize, nj as usize)) {
        pre.insert((ni as usize, nj as usize), (i, j));
        q.push_back((ni as usize, nj as usize));
      }
    }
  }
  if !pre.contains_key(&end) {
    Vec::new()
  } else {
    let mut ptr = end;
    let mut res = vec![ptr];
    while ptr != start {
      ptr = pre.get(&ptr).unwrap().clone();
      res.push(ptr);
    }
    res.reverse();
    res
  }
}

Ankeet Parikh

ankeetparikh

5 months ago

4.66ms

89.29kb

use std::collections::{HashMap, HashSet, VecDeque};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
      if maze.len() == 0 || maze[0].len() == 0 {
    return Vec::new()
  }
  let n = maze.len() as i32;
  let m = maze[0].len() as i32;
  println!("n={} m={}", n, m);
  let dirs: Vec<(i32, i32)> = vec![(0, 1), (0, -1), (1, 0), (-1, 0)];
  let mut pre = HashMap::new();
  pre.insert(start, (100000, 100000));
  let mut q = VecDeque::new();
  q.push_back(start);
  while q.len() > 0 {
    let (i, j) = q.pop_front().unwrap();
    // println!("Doing {} {}", i, j);
    for (di, dj) in &dirs {
      let (ni, nj) = (i as i32 + di, j as i32 + dj);
      // println!("Neighbor {} {}", ni, nj);
      if 0 <= ni && ni < n && 0 <= nj && nj < m && maze[ni as usize][nj as usize] != '#' && !pre.contains_key(&(ni as usize, nj as usize)) {
        pre.insert((ni as usize, nj as usize), (i, j));
        q.push_back((ni as usize, nj as usize));
      }
    }
  }
  if !pre.contains_key(&end) {
    Vec::new()
  } else {
    let mut ptr = end;
    let mut res = vec![ptr];
    while ptr != start {
      ptr = pre.get(&ptr).unwrap().clone();
      res.push(ptr);
    }
    res.reverse();
    res
  }
}

Markus Bergkvist

mbergkvist

5 months ago

7.22ms

89.51kb

use std::collections::{HashSet, VecDeque};
const WALL: char = '#';
const END: char = 'E';
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    _end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut paths = VecDeque::from([vec![start]]);
    let mut visited = HashSet::from([start]);
    loop {
        while let Some(path) = paths.pop_front() {
            let origin = path
                .last()
                .expect("All paths should have at least one element");
            let neighbours = neighbours(&maze, origin);
            for neighbour in neighbours.difference(&visited) {
                let tile = tile(&maze, neighbour);
                if tile.is_wall() {
                    continue;
                }
                let mut path = path.clone();
                path.push(neighbour.clone());
                if tile.is_end() {
                    return path;
                }
                paths.push_back(path);
            }
            visited.extend(neighbours);
        }
        return vec![];
    }
}
fn neighbours(maze: &Vec<Vec<char>>, origin: &(usize, usize)) -> HashSet<(usize, usize)> {
    let height = maze.len();
    let widht = maze[0].len();
    vec![
        (origin.0.saturating_sub(1), origin.1),
        (origin.0, origin.1.saturating_sub(1)),
        (origin.0, std::cmp::min(widht - 1, origin.1 + 1)),
        (std::cmp::min(height - 1, origin.0 + 1), origin.1),
    ]
    .into_iter()
    .filter(|pos| pos != origin)
    .collect()
}
fn tile(maze: &Vec<Vec<char>>, position: &(usize, usize)) -> char {
    maze[position.0][position.1]
}
trait Position {
    fn is_wall(&self) -> bool;
    fn is_end(&self) -> bool;
}
impl Position for char {
    fn is_wall(&self) -> bool {
        self == &WALL
    }
    fn is_end(&self) -> bool {
        self == &END
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_tile() {
        let maze: Vec<Vec<char>> = vec![vec!['.', 'S'], vec!['E', '#']];
        assert!(tile(&maze, &(1, 0)).is_end());
        assert!(tile(&maze, &(1, 1)).is_wall());
    }
    #[test]
    fn test_neighbour() {
        let maze: Vec<Vec<char>> = vec![
            vec!['S', '.', '.'],
            vec!['.', '#', '.'],
            vec!['.', '.', 'E'],
        ];
        assert_eq!(neighbours(&maze, &(0, 0)), HashSet::from([(0, 1), (1, 0)]));
        assert_eq!(
            neighbours(&maze, &(1, 1)),
            HashSet::from([(0, 1), (1, 0), (1, 2), (2, 1),])
        );
        assert_eq!(neighbours(&maze, &(2, 2)), HashSet::from([(1, 2), (2, 1)]));
    }
}

Kentaro Abe

abekem

5 months ago

14.29ms

89.08kb

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut queue: VecDeque<((usize, usize), Vec<(usize, usize)>)> = VecDeque::new();
    let y_max = maze.capacity();
    let x_max = maze[0].capacity();
    let mut visited = vec!(vec!(false; x_max); y_max);
    queue.push_back((start, vec![start]));
    loop {
        if queue.is_empty() {
            return vec![];
        }
        let (current, path) = queue.pop_front().unwrap();
        visited[current.0][current.1] = true;
        if current == end {
            return path;
        }
        let left = (current.0, current.1.wrapping_sub(1));
        if left.1 < x_max && maze[left.0][left.1] != '#' && !visited[left.0][left.1] {
            let mut next = path.clone();
            next.push(left);
            queue.push_back((left, next));
        }
        let right = (current.0, current.1.wrapping_add(1));
        if right.1 < x_max && maze[right.0][right.1] != '#' && !visited[right.0][right.1] {
            let mut next = path.clone();
            next.push(right);
            queue.push_back((right, next));
        }
        let down = (current.0.wrapping_sub(1), current.1);
        if down.0 < y_max && maze[down.0][down.1] != '#' && !visited[down.0][down.1] {
            let mut next = path.clone();
            next.push(down);
            queue.push_back((down, next));
        }
        let up = (current.0.wrapping_add(1), current.1);
        if up.0 < y_max && maze[up.0][up.1] != '#' && !visited[up.0][up.1] {
            let mut next = path.clone();
            next.push(up);
            queue.push_back((up, next));
        }
    }
}

ludovicknecht

5 months ago

3.74ms

89.39kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    
    let mut maze_solver = MazeSolver::new(maze, start, end);
    maze_solver.solve_maze()
}
type Cell = (usize, usize);
pub enum Outcome {
    StepsIndexes(Vec<u128>),
    EndIndex(u128),
    NoSolution,
}
pub struct Step<T> {
    from_index: Option<u128>,
    pub to: T,
}
impl<T> Step<T> {
    pub fn new(from_index: u128, to: T) -> Self {
        Step {
            from_index: Some(from_index),
            to
        }
    }
}
struct MazeSolver {
    maze: Vec<Vec<char>>,
    start: Cell,
    end: Cell,
    visited: Vec<Vec<bool>>,
    paths: Vec<Step<Cell>>,
    length: usize,
    width: usize,
}
impl MazeSolver {
    pub fn new(maze: Vec<Vec<char>>, start: Cell, end: Cell) -> Self {
        Self {
            maze,
            start,
            end,
            visited: Vec::new(),
            paths: Vec::new(),
            length: 0,
            width: 0,
        }
    }
    fn init(&mut self) {
        self.length = self.maze.len();
        self.width = self.maze[0].len();
        self.visited = vec![vec![false; self.width]; self.length];
        self.visited[self.start.0][self.start.1] = true;
        self.paths.push(Step::<Cell> {from_index: None, to: self.start});
    }
    fn is_cell_available(&self, cell: &Cell) -> bool {
        self.maze[cell.0][cell.1] != '#' && self.visited[cell.0][cell.1] == false
    }
    fn add_cell_if_available(&mut self, cell: &Cell, cells: &mut Vec<Cell>) {
        if self.is_cell_available(&cell) {
            self.visited[cell.0][cell.1] = true;
            cells.push(*cell);
        }
    }
    fn get_next_cells_for_single_cell(&mut self, current: &Cell) -> Vec<Cell> {
        let mut cells: Vec<Cell> = Vec::new();
        if current.0 > 0 {
            let cell = (current.0 - 1, current.1);
            self.add_cell_if_available(&cell, &mut cells);
        }
        if current.0 < self.length - 1 {
            let cell = (current.0 + 1, current.1);
            self.add_cell_if_available(&cell, &mut cells);
        }
        if current.1 > 0 {
            let cell = (current.0, current.1 - 1);
            self.add_cell_if_available(&cell, &mut cells);
        }
        if current.1 < self.width - 1 {
            let cell = (current.0, current.1 + 1);
            self.add_cell_if_available(&cell, &mut cells);
        }
        cells
    }
    fn get_next_steps_index(&mut self, current_indexes: &Vec<u128>) ->  Outcome {
        let mut new_steps_indexes = Vec::<u128>::new();
        let mut step_index = self.paths.len() as u128;
        let mut cells = Vec::<Cell>::new();
        
        for index in current_indexes {
            cells.push(self.paths[*index as usize].to);
        }
        for (count, &cell) in cells.iter().enumerate() {
            let next_cells = self.get_next_cells_for_single_cell(&cell);
        
            for next_cell in next_cells {
                self.paths.push(Step::<Cell>::new( current_indexes[count], next_cell));
                new_steps_indexes.push(step_index);
                
                if next_cell == self.end {
                    return Outcome::EndIndex(step_index);
                }
                step_index += 1;
            }
        }
        if new_steps_indexes.len() == 0 {
            return Outcome::NoSolution;
        }
        Outcome::StepsIndexes(new_steps_indexes)
    }
    pub fn solve_maze(&mut self) -> Vec<Cell> {
        self.init();
        let mut steps_indexes = Outcome::StepsIndexes(vec![0 as u128]);
        while let Outcome::StepsIndexes(indexes) = steps_indexes {
            steps_indexes = match self.get_next_steps_index(&indexes) {
                Outcome::StepsIndexes(new_indexes) => Outcome::StepsIndexes(new_indexes),
                Outcome::NoSolution => return Vec::new(),
                Outcome::EndIndex(end_index) => return self.compute_shortest_path(end_index),
            };
        }
        Vec::new()
    }
    fn compute_shortest_path(&self, end_index: u128) -> Vec<Cell> {
        let mut step = &self.paths[end_index as usize];
        let mut shortest_path = vec![step.to];
        let mut from_index = step.from_index;
        while let Some(i) = from_index {
            step = &self.paths[i as usize];
            shortest_path.push(step.to);
            from_index = step.from_index;
        }
        shortest_path.reverse();
        shortest_path
    }
}

Stefan Roas

sroas

5 months ago

4.25ms

88.64kb

use std::collections::{HashMap, VecDeque};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let directions = [(1i64, 0i64), (0i64, 1i64), (-1i64, 0i64), (0i64, -1i64)];
    let mut queue = VecDeque::new();
    let mut visited = HashMap::new();
    visited.insert(start, None::<(usize, usize)>);
    queue.push_back(start);
    while let Some(entry) = queue.pop_front() {
        if entry == end {
            break;
        }
        directions.iter().for_each(|direction| {
            let rownr = entry.0 as i64 + direction.0;
            let colnr = entry.1 as i64 + direction.1;
            if rownr < 0 || colnr < 0 {
                return;
            }
            if visited.contains_key(&(rownr as usize, colnr as usize)) {
                return;
            }
            if let Some(row) = maze.get(rownr as usize) {
                if let Some(cell) = row.get(colnr as usize) {
                    if *cell != '#' {
                        visited.insert((rownr as usize, colnr as usize), Some(entry));
                        queue.push_back((rownr as usize, colnr as usize));
                    }
                }
            }
        });
    }
    let mut key = end;
    let mut path = Vec::with_capacity(visited.len());
    while let Some(entry) = visited.get_key_value(&key) {
        path.push(*entry.0);
        if entry.1.is_none() {
            break;
        }
        key = entry.1.expect("will never fail");
    }
    path.reverse();
    if visited.contains_key(&end) {
        path
    } else {
        vec![]
    }
}

Masayuki Sunahara

tamanishi

5 months ago

3.31ms

88.95kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let height = maze.len();
    let width = maze[0].len();
    let mut visited = maze.to_vec();
    let mut path = vec![vec![-1; width]; height];
    let d4: Vec<(i32, i32)> = vec![(-1, 0), (0, -1), (1, 0), (0, 1)];
    // for line in maze {
    //     println!("{:?}", line);
    // }
    visited[start.0][start.1] = '#';
    let mut vd = std::collections::VecDeque::new();
    vd.push_back(start);
    // println!("end ----> {:?}", end);
    let mut step = -1;
    let mut arrived = false;
    while vd.len() > 0 {
        let point = vd.pop_front().unwrap();
        for i in 0..4 {
            let x = point.1.wrapping_add(d4[i].1 as usize);
            let y = point.0.wrapping_add(d4[i].0 as usize);
            if x >= width || y >= height {
                continue;
            }
            if visited[y][x] == '.' {
                vd.push_back((y, x));
                visited[y][x] = '#';
                path[y][x] = path[point.0][point.1] + 1;
                step = path[point.0][point.1] + 1;
                // println!("path[{}][{}] ----> {}", y, x, path[y][x]);
            }
            if (y, x) == end {
                arrived = true;
            } 
        }
    }
    if arrived == false  {
        return vec![];
    }
    path[end.0][end.1] = step + 1;
    // println!("path[{}][{}] ----> {}", end.0, end.1, path[end.0][end.1]);
    // for line in path.clone().into_iter() {
    //     println!("{:?}", line);
    // }
    let mut route = std::collections::VecDeque::new();
    route.push_front((end.0, end.1));
    let mut x = end.1;
    let mut y = end.0;
    let mut cur_step = path[end.0][end.1];
    for _i in (0..path[y][x]).rev() {
        // println!("i -------> {:?}", i);
        let mut cur_point = (0, 0);
        for j in 0..4 {
            let temp_x = x.wrapping_add(d4[j].1 as usize);
            let temp_y = y.wrapping_add(d4[j].0 as usize);
            if temp_x >= width || temp_y >= height {
                continue;
            }
            // choose smallest step
            if path[temp_y][temp_x] == -1 {
                continue;
            }
            // println!("cur_step ----> {}", cur_step);
            // println!("path[temp_y][temp_x] ----> {}", path[temp_y][temp_x]);
            if path[temp_y][temp_x] < cur_step {
                cur_step = path[temp_y][temp_x];
                cur_point = (temp_y, temp_x);
            }
        }
        if cur_point == start {
            break;
        }
        x = cur_point.1;
        y = cur_point.0;
        route.push_front(cur_point);
    }
    route.push_front((start.0, start.1));
    Vec::from(route)
}

Ando “Thor” Nando

DivineGod

5 months ago

3.54ms

89.19kb

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    const ROAD: char = '.';
    const GOAL: char = 'E';
    let rows = maze.len();
    let cols = maze[0].len();
    let mut queue = VecDeque::new();
    queue.push_back((start.0, start.1, vec![start]));
    let mut visited = vec![];
    while queue.len() > 0 {
        if let Some((x, y, routes)) = queue.pop_front() {
            if (x, y) == end {
                return routes
            }
            for allow in ["R", "L", "U", "D"] {
                let (nx, ny) = match allow {
                    "R" => {
                        (x.wrapping_add(1), y)
                    },
                    "L" => {
                        (x.wrapping_sub(1), y)
                    },
                    "U" => {
                        (x, y.wrapping_sub(1))
                    },
                    "D" => {
                        (x, y.wrapping_add(1))
                    },
                    _ => {panic!("error")}
                };
                if nx < rows && ny < cols && (maze[nx][ny] == ROAD || maze[nx][ny] == GOAL) && !visited.contains(&(nx, ny)) {
                    visited.push((nx, ny));
                    let mut new_routes = routes.clone();
                    new_routes.push((nx, ny));
                    queue.push_back((nx, ny, new_routes));
                }
            }
        }
    }
    vec![]
}

James Starkman

jstarkman

6 months ago

4.27ms

88.64kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    // (y, x)
    start: (usize, usize),
    // (y, x)
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let height = maze.len();
    if height == 0 {
        return vec![]; // FIXME This function should return a Result, not always Vec.
    }
    let width = maze[0].len();
    if width == 0 {
        return vec![]; // FIXME ibid
    }
    let is_ragged = maze.iter().any(|row| row.len() != width);
    if is_ragged {
        return vec![]; // FIXME ibid
    }
    if start.0 >= height || start.1 >= width {
        return vec![]; // FIXME ibid
    }
    if end.0 >= height || end.1 >= width {
        return vec![]; // FIXME ibid
    }
    let Some(distances) = measure_distances(&maze, start, end)
        else { return vec![]; /* FIXME ibid */ };
    let shortest_path = shortest_path(&maze, &distances, end);
    shortest_path
}
const WALL: char = '#';
fn measure_distances(
    maze: &Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Option<Vec<Vec<u32>>> {
    let height = maze.len();
    let width = maze[0].len();
    let mut distances = vec![vec![0; width]; height];
    for (m_row, d_row) in maze.iter().zip(distances.iter_mut()) {
        for (t, d) in m_row.iter().zip(d_row.iter_mut()) {
            if *t == WALL {
                *d = u32::MAX;
            }
        }
    }
    // Why use a VecDeque/counter when swapping buffers is harder to break?
    let mut active = vec![];
    active.push(start);
    let mut future = vec![];
    let mut steps = 0;
    let mut can_reach_end = false;
    while !active.is_empty() {
        for (y, x) in active.drain(..) {
            if (y, x) == end {
                can_reach_end = true;
            }
            if distances[y][x] > 0 {
                continue;
            }
            distances[y][x] = steps;
            for (xx, yy) in NeighborIterator::new(height, width, x, y, false) {
                // reduces churn
                if distances[yy][xx] > 0 {
                    continue;
                }
                future.push((yy, xx));
            }
        }
        std::mem::swap(&mut active, &mut future);
        steps += 1;
    }
    distances[start.1][start.0] = 0; // avoids condition in loop
    can_reach_end.then_some(distances)
}
fn shortest_path(
    maze: &Vec<Vec<char>>,
    distances: &Vec<Vec<u32>>,
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let height = maze.len();
    let width = maze[0].len();
    let mut retval = vec![end];
    loop {
        let (y, x) = retval.last().unwrap().clone();
        let d = distances[y][x];
        if d == 0 { // proxy for start
            break;
        }
        for (xx, yy) in NeighborIterator::new(height, width, x, y, false) {
            let dd = distances[yy][xx];
            if d - 1 == dd {
                retval.push((yy, xx));
                break;
            }
        }
    }
    retval.reverse();
    retval
}
//region Iterator over neighboring tiles in a grid; four- or eight-connected.
struct NeighborIterator {
    height: isize,
    width: isize,
    x: isize,
    y: isize,
    scan_index: usize,
    connect: usize,
}
impl NeighborIterator {
    fn new(
        height: usize,
        width: usize,
        x: usize,
        y: usize,
        is_eight_connected: bool,
    ) -> NeighborIterator {
        Self {
            height: height as isize,
            width: width as isize,
            x: x as isize,
            y: y as isize,
            scan_index: 0,
            connect: 4 * (is_eight_connected as usize + 1),
        }
    }
    const OFFSETS4: [(isize, isize); 4] = [(0, -1), (-1, 0), (1, 0), (0, 1)];
    const OFFSETS8: [(isize, isize); 8] = [
        (-1, -1), (0, -1), (1, -1),
        (-1, 0), /*0,0*/ (1, 0),
        (-1, 1), (0, 1), (1, 1),
    ];
}
impl Iterator for NeighborIterator {
    type Item = (usize, usize);
    fn next(&mut self) -> Option<Self::Item> {
        while self.scan_index < self.connect {
            let (dx, dy) = match self.connect {
                4 => NeighborIterator::OFFSETS4[self.scan_index].clone(),
                8 => NeighborIterator::OFFSETS8[self.scan_index].clone(),
                _ => unreachable!(),
            };
            self.scan_index += 1;
            let c = (self.x + dx, self.y + dy);
            let can_dx = 0 <= c.0 && c.0 < self.width;
            let can_dy = 0 <= c.1 && c.1 < self.height;
            if can_dx && can_dy {
                return Some((c.0 as usize, c.1 as usize));
            }
        }
        None
    }
}
//endregion

Diego Maia

diegocmsantos

6 months ago

5.54ms

89.35kb

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut queue = VecDeque::new();
    let mut visited = vec![vec![false; maze[0].len()]; maze.len()];
    let mut path = vec![vec![None; maze[0].len()]; maze.len()];
    let dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)];
    visited[start.0][start.1] = true;
    queue.push_back(start);
    while let Some(current) = queue.pop_front() {
        if current == end {
            // Found
            let mut p = vec![];
            let mut current = Some(end);
            while let Some(c) = current {
                p.push(c);
                current = path[c.0][c.1];
            }
            p.reverse();
            return p;
        } else {
            // Visit
            let (x, y) = current;
            for &(dx, dy) in &dirs {
                let nx = x.wrapping_add_signed(dx);
                let ny = y.wrapping_add_signed(dy);
                if nx < maze.len() && ny < maze[0].len() 
                        && maze[nx][ny] != '#' && !visited[nx][ny] {
                    path[nx][ny] = Some((x, y));
                    visited[nx][ny] = true;
                    queue.push_back((nx, ny));
                }
            }
        }
    }
    
    // Not Found
    vec![]
}

Jun Huang

leemars

6 months ago

4.94ms

89.35kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    use std::collections::VecDeque;
    let mut queue = VecDeque::new();
    let mut visited = vec![vec![false; maze[0].len()]; maze.len()];
    let mut path = vec![vec![None; maze[0].len()]; maze.len()];
    let dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)];
    visited[start.0][start.1] = true;
    queue.push_back(start);
    while let Some(current) = queue.pop_front() {
        if current == end {
            // Found
            let mut p = vec![];
            let mut current = Some(end);
            while let Some(c) = current {
                p.push(c);
                current = path[c.0][c.1];
            }
            p.reverse();
            return p;
        } else {
            // Visit
            let (x, y) = current;
            for &(dx, dy) in &dirs {
                let nx = x.wrapping_add_signed(dx);
                let ny = y.wrapping_add_signed(dy);
                if nx < maze.len() && ny < maze[0].len() 
                        && maze[nx][ny] != '#' && !visited[nx][ny] {
                    path[nx][ny] = Some((x, y));
                    visited[nx][ny] = true;
                    queue.push_back((nx, ny));
                }
            }
        }
    }
    
    // Not Found
    vec![]
}

MichaelScofield

MichaelScofield111

6 months ago

3.84ms

89.06kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let mut visited = vec![vec![false; maze[0].len()]; maze.len()];
    let mut path = Vec::new();
    let mut best_path = Vec::new();
    search_path(&maze, &mut visited, start, end, &mut path, &mut best_path);
    best_path
}
fn search_path(maze: &Vec<Vec<char>>, visited: &mut Vec<Vec<bool>>, position: (usize, usize), end: (usize, usize), path: &mut Vec<(usize, usize)>, best_path: &mut Vec<(usize, usize)>,) {
    if position.0 >= maze.len() || position.1 >= maze[0].len() || maze[position.0][position.1] == '#' || visited[position.0][position.1] {
        return;
    }
    path.push(position);
    visited[position.0][position.1] = true;
    if position == end {
        if best_path.is_empty() || path.len() < best_path.len() {
            best_path.clear();
            best_path.extend_from_slice(path);
        }
    }
    else{
        let directions = vec![(0, 1), (1, 0), (0, -1), (-1, 0)];
        for direction in directions {
            let new_position = (
                position.0 as i32 + direction.0,
                position.1 as i32 + direction.1,
            );
            if new_position.0 >= 0 && new_position.1 >= 0 {
                search_path(
                    maze,
                    visited,
                    (new_position.0 as usize, new_position.1 as usize),
                    end,
                    path,
                    best_path,
                );
            }
        }
    }
    path.pop();
    visited[position.0][position.1] = false;
}

Elizabeth Doughty

Thymelizabeth

6 months ago

4.23ms

89.15kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let mut result = vec![vec![start]];
    loop {
        let old_result = result.clone();
        result = result
            .iter()
            .flat_map(|path| {
                [(1, 0), (-1, 0), (0, 1), (0, -1)]
                    .into_iter()
                    .filter_map(|(drow, dcol)| {
                        let (r, c) = path.iter().last()?;
                        let (r2, c2) = (r.wrapping_add_signed(drow), c.wrapping_add_signed(dcol));
                        let next = maze.get(r2).and_then(|row| row.get(c2))?;
                        if matches!(next, 'E' | '.') && !path.contains(&(r2, c2)) {
                            let mut new_path = path.clone();
                            new_path.push((r2, c2));
                            Some(new_path)
                        } else {
                            None
                        }
                    })
            })
            .collect();
        if result
            .iter()
            .any(|path| path.last().is_some_and(|l| *l == end))
            || result == old_result
        {
            break result
                .into_iter()
                .find(|path| path.last() == Some(&end))
                .unwrap_or(vec![]);
        }
    }
}

Sh!n0bu

shinobu52

6 months ago

3.58ms

89.06kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let mut visited = vec![vec![false; maze[0].len()]; maze.len()];
    let mut path = Vec::new();
    let mut best_path = Vec::new();
    search_path(&maze, &mut visited, start, end, &mut path, &mut best_path);
    best_path
}
fn search_path(
    maze: &Vec<Vec<char>>,
    visited: &mut Vec<Vec<bool>>,
    position: (usize, usize),
    end: (usize, usize),
    path: &mut Vec<(usize, usize)>,
    best_path: &mut Vec<(usize, usize)>,
) {
    if position.0 >= maze.len()
        || position.1 >= maze[0].len()
        || maze[position.0][position.1] == '#'
        || visited[position.0][position.1]
    {
        return;
    }
    path.push(position);
    visited[position.0][position.1] = true;
    if position == end {
        if best_path.is_empty() || path.len() < best_path.len() {
            best_path.clear();
            best_path.extend_from_slice(path);
        }
    } else {
        let directions = vec![(0, 1), (1, 0), (0, -1), (-1, 0)];
        for direction in directions {
            let new_position = (
                position.0 as i32 + direction.0,
                position.1 as i32 + direction.1,
            );
            if new_position.0 >= 0 && new_position.1 >= 0 {
                search_path(
                    maze,
                    visited,
                    (new_position.0 as usize, new_position.1 as usize),
                    end,
                    path,
                    best_path,
                );
            }
        }
    }
    path.pop();
    visited[position.0][position.1] = false;
}

0xsmarter

6 months ago

3.73ms

89.23kb

fn dfs(
    maze: &Vec<Vec<char>>,
    states: &mut Vec<Vec<bool>>,
    (x, y): (usize, usize),
    end: (usize, usize),
    path: &mut Vec<(usize, usize)>
) -> bool {
    path.push((x, y));
    states[x][y] = true;
    
    if (x, y) == end {
        return true;
    }
    let (r, c) = (maze.len(), maze[0].len());
    
    let neighbors = vec![(-1, 0), (1, 0), (0, -1), (0, 1)].into_iter()
        .filter_map(|(dx, dy)| {
            let nx = (x as i32) + dx;
            let ny = (y as i32) + dy;
            if nx < 0 || ny < 0 {
                return None;
            }
            let (nx, ny) = (nx as usize, ny as usize);
            if nx < r && ny < c && maze[nx][ny] != '#' {
                Some((nx, ny))
            } else {
                None
            }
        })
        .filter(|&(nx, ny)| !states[nx][ny])
        .collect::<Vec<_>>();
    
    for n in neighbors {
        if dfs(maze, states, n, end, path) {
            return true;
        }
    }
    path.pop();
    return false;
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let (r, c) = (maze.len(), maze[0].len());
    let mut path = Vec::new();
    let mut states = vec![vec![false; c]; r];
    if dfs(&maze, &mut states, start, end, &mut path) {
        path
    } else {
        Vec::new()
    }
}

Andrea Ciprietti

cip999

6 months ago

4.67ms

89.23kb

fn dfs(
    maze: &Vec<Vec<char>>,
    states: &mut Vec<Vec<bool>>,
    (x, y): (usize, usize),
    end: (usize, usize),
    path: &mut Vec<(usize, usize)>
) -> bool {
    path.push((x, y));
    states[x][y] = true;
    
    if (x, y) == end {
        return true;
    }
    let (r, c) = (maze.len(), maze[0].len());
    
    let neighbors = vec![(-1, 0), (1, 0), (0, -1), (0, 1)].into_iter()
        .filter_map(|(dx, dy)| {
            let nx = (x as i32) + dx;
            let ny = (y as i32) + dy;
            if nx < 0 || ny < 0 {
                return None;
            }
            let (nx, ny) = (nx as usize, ny as usize);
            if nx < r && ny < c && maze[nx][ny] != '#' {
                Some((nx, ny))
            } else {
                None
            }
        })
        .filter(|&(nx, ny)| !states[nx][ny])
        .collect::<Vec<_>>();
    
    for n in neighbors {
        if dfs(maze, states, n, end, path) {
            return true;
        }
    }
    path.pop();
    return false;
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let (r, c) = (maze.len(), maze[0].len());
    let mut path = Vec::new();
    let mut states = vec![vec![false; c]; r];
    if dfs(&maze, &mut states, start, end, &mut path) {
        path
    } else {
        Vec::new()
    }
}