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

Algorab

7 hours ago

4.08ms

89.34kb

use std::collections::{HashMap, HashSet, 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 = HashSet::new();
    let mut parent = HashMap::new();
    queue.push_back(start);
    visited.insert(start);
    let dirs: [(isize, isize); 4] = [(1, 0), (-1, 0), (0, 1), (0, -1)];
    let rows = maze.len() as isize;
    let cols = maze[0].len() as isize;
    while let Some((r, c)) = queue.pop_front() {
        if (r, c) == end {
            let mut path = vec![end];
            let mut cur = end;
            while cur != start {
                cur = parent[&cur];
                path.push(cur);
            }
            path.reverse();
            return path;
        }
        for (dr, dc) in dirs {
            let nr = r as isize + dr;
            let nc = c as isize + dc;
            if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
                continue;
            }
            let nr_u = nr as usize;
            let nc_u = nc as usize;
            if maze[nr_u][nc_u] != '#' && !visited.contains(&(nr_u, nc_u)) {
                visited.insert((nr_u, nc_u));
                parent.insert((nr_u, nc_u), (r, c));
                queue.push_back((nr_u, nc_u));
            }
        }
    }
    vec![]
}

manu3618

9 days ago

5.91ms

100.75kb

use std::collections::HashMap;
/// Sequence of coords:
/// 
/// (line, column)
/// line 0: the upper one
/// column 0: the most left one
#[derive(Default, Debug, Clone)]
pub struct Path(Vec<(usize, usize)>);
impl Path {
    fn cost(&self) -> usize {
        self.0.len()
    }
    pub fn from_starting_point(s: (usize, usize)) -> Self {
        Self(vec![s])
    }
    fn add_point(&self, p: (usize, usize)) -> Self {
        let mut inner = self.0.clone();
        inner.push(p);
        Self(inner)
    }
    pub fn extend(&self, max_col: usize, max_line: usize) -> Vec<Self> {
        if self.0.is_empty() {
            return Vec::new();
        }
        get_neighbours(self.0.last().unwrap().clone(), max_col, max_line).iter().map(|&p| self.add_point(p)).collect()
    }
    fn last(&self) -> (usize, usize) {
        self.0.last().unwrap().clone()
    }
}
fn get_neighbours(s: (usize, usize), max_col: usize, max_line: usize) -> Vec<(usize, usize)> {
    let mut v = Vec::new();
    if s.0 > 0 {
        v.push((s.0 - 1, s.1));
    }
    if s.0 < max_line - 1 {
        v.push((s.0 + 1, s.1));
    }
    if s.1 > 0 {
        v.push((s.0, s.1 - 1));
    }
    if s.1 < max_col - 1 {
        v.push((s.0, s.1 + 1));
    }
    v 
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let mut paths = HashMap::new();
    let max_line = maze.len();
    if dbg!(max_line)  == 0 {
        return Vec::new();
    }
    let max_col = maze[0].len();
    if dbg!(max_col) == 0 {
        return Vec::new();
    }
    paths.insert(start, Path::from_starting_point(start));
    let mut paths_num = paths.len();
    for _ in 0..1000000 {
        let mut new_paths = Vec::new();
        for cur_paths in paths.values() {
            new_paths.append(&mut cur_paths.extend(max_col, max_line))
        }
        for new_path in new_paths {
            let end = new_path.last();
            if maze[end.0][end.1] == '#' {
                continue;
            }
            let cur_path: Path = match paths.get(&end){
                Some(x) => x.clone(),
                None => Default::default(),
            };
            if new_path.cost() < cur_path.cost() || cur_path.cost() == 0 {
                let _  = paths.insert(new_path.last(), new_path);
            }
        }
        if paths.len() == paths_num {
            break;
        }
        paths_num = paths.len();
    }
    paths.entry(end).or_default().0.clone()
}

Wouter

WouterMartens

24 days ago

3.54ms

89.15kb

use std::collections::{HashMap, VecDeque};
type Position = (usize, usize);
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: Position,
    end: Position,
) -> Vec<Position> {
    let (rows, cols) = (maze.len(), maze[0].len());
    let mut queue = VecDeque::from([start]);
    let mut visited = vec![vec![false; cols]; rows];
    let mut came_from = HashMap::new();
    visited[start.0][start.1] = true;
    const DIRECTIONS: [(isize, isize); 4] = [
        (0, 1),
        (0, -1),
        (1, 0),
        (-1, 0),
    ];
    while let Some(pos) = queue.pop_front() {
        if pos == end {
            return reconstruct_path(came_from, start, end);
        }
        for (dx, dy) in DIRECTIONS {
            if let Some(next_pos) = get_next_position(pos, dx, dy, rows, cols) {
                let (nx, ny) = next_pos;
                if !visited[nx][ny] && maze[nx][ny] != '#' {
                    visited[nx][ny] = true;
                    queue.push_back(next_pos);
                    came_from.insert(next_pos, pos);
                }
            }
        }
    }
    Vec::new()
}
fn get_next_position(
    (x, y): Position,
    dx: isize,
    dy: isize,
    rows: usize,
    cols: usize,
) -> Option<Position> {
    let nx = x.checked_add_signed(dx)?;
    let ny = y.checked_add_signed(dy)?;
    if nx < rows && ny < cols {
        Some((nx, ny))
    } else {
        None
    }
}
fn reconstruct_path(
    came_from: HashMap<Position, Position>,
    start: Position,
    end: Position,
) -> Vec<Position> {
    if !came_from.contains_key(&end) {
        return Vec::new();
    }
    let mut path = Vec::new();
    let mut current = end;
    while current != start {
        path.push(current);
        current = came_from[&current];
    }
    path.push(start);
    path.reverse();
    path
}

whhc

a month ago

4.16ms

89.35kb

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![];
    }
    let cols = maze[0].len();
    let directions = [(-1, 0), (0, 1), (1, 0), (0, -1)];
    let mut prev: Vec<Vec<Option<(usize, usize)>>> = vec![vec![None; cols]; rows];
    let mut visited = vec![vec![false; cols]; rows];
    let mut queue = VecDeque::new();
    queue.push_back(start);
    visited[start.0][start.1] = true;
    while let Some((r, c)) = queue.pop_front() {
        if (r, c) == end {
            return reconstruct_path(prev, end);
        }
        for (dr, dc) in &directions {
            let nr = r as i32 + dr;
            let nc = c as i32 + dc;
            if nr >= 0 && nr < rows as i32 && nc >= 0 && nc < cols as i32 {
                let nr = nr as usize;
                let nc = nc as usize;
                if ['E', '.'].contains(&maze[nr][nc]) && !visited[nr][nc] {
                    visited[nr][nc] = true;
                    prev[nr][nc] = Some((r, c));
                    queue.push_back((nr, nc));
                }
            }
        }
    }
    vec![]
}
pub fn reconstruct_path(
    prev: Vec<Vec<Option<(usize, usize)>>>,
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path = Vec::new();
    let mut current = end;
    while let Some(pre_step) = prev[current.0][current.1] {
        path.push(current);
        current = pre_step;
    }
    path.push(current);
    path.reverse();
    path
}

medzernik

a month ago

3.94ms

89.63kb

use std::collections::HashMap;
pub enum Direction {
    North,
    South,
    East,
    West,
}
pub fn step(maze: &Vec<Vec<char>>, (x, y): &(usize, usize), dir: &Direction) -> Option<(usize, usize)> {
    let mut x = *x;
    let mut y = *y;
    match *dir {
        Direction::North => {
            if x == 0 { return None }
            x -= 1;
        },
        Direction::South => {
            if x + 1 >= maze.len() { return None }
            x += 1;
        },
        Direction::East => {
            if y + 1 >= maze[x].len() { return None; }
            y += 1;
        },
        Direction::West => {
            if y == 0 { return None; }
            y -= 1;
        },
    }
    if maze[x][y] == '.' || maze[x][y] == 'E' {
        Some ((x, y))
    } else {
        None
    }
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    {
        let (x, y) = start;
        if maze[x][y] != 'S' {
            return vec![];
        }
        let (x, y) = end;
        if maze[x][y] != 'E' {
            return vec![];
        }
    }
    let directions = vec![Direction::North, Direction::South, Direction::East, Direction::West];
    let mut state = HashMap::new();
    let mut todo = vec![start];
    state.insert(start, (0, start));
    while todo.len() > 0 {
        let cur = todo.pop().unwrap();
        let (distance, _) = &state.get(&cur).unwrap();
        let distance = distance.clone();
        for dir in &directions {
            if let Some(next) = step(&maze, &cur, dir) {
                match state.get(&next) {
                    Some( (d, _)) if distance >= *d => (),
                    _ => {
                        state.insert(next, (distance + 1, cur));
                        todo.push(next);
                    }
                }
            }
        }
    }
    match state.get(&end) {
        None => vec![],
        Some((_, prev)) => {
            let mut revres = vec![end, *prev];
            let mut pos = *prev;
            while pos != start {
                (_, pos) = *state.get(&pos).unwrap();
                revres.push(pos);
            }
            revres.into_iter().rev().collect()
        }
    }
}

Baron Curtin

baroncurtin2

a month ago

4.00ms

89.19kb

use std::collections::{VecDeque, HashMap};
pub fn is_valid_cell(maze: &[Vec<char>], pos: (usize, usize)) -> bool {
    let cell = maze[pos.0][pos.1];
    cell == '.' || cell == 'S' || cell == 'E'
}
pub fn reconstruct_path(
    parent: &HashMap<(usize, usize), (usize, usize)>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path = Vec::new();
    let mut current = end;
    // backtrack from end to start
    while current != start {
        path.push(current);
        current = parent[&current];
    }
    path.push(start);
    path.reverse();
    path
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    if maze.is_empty() || maze[0].is_empty() {
        return Vec::new();
    }
    let rows = maze.len();
    let cols = maze[0].len();
    // validate start and end positions
    if start.0 >= rows || start.1 >= cols || end.0 >= rows || end.1 >= cols {
        return Vec::new();
    }
    if start == end {
        return vec![start];
    }
    // BFS set up
    let mut queue = VecDeque::new();
    let mut visited = vec![vec![false; cols]; rows];
    let mut parent: HashMap<(usize, usize), (usize, usize)> = HashMap::new();
    // Start BFS
    queue.push_back(start);
    visited[start.0][start.1] = true;
    // Directions: up, down, left, right
    let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)];
    while let Some(current) = queue.pop_front() {
        // check if at the end
        if current == end {
            return reconstruct_path(&parent, start, end);
        }
        // explore all 4 directions
        for (dr, dc) in directions {
            let new_row = current.0 as i32 + dr;
            let new_col = current.1 as i32 + dc;
            // check bounds
            if new_row >= 0 && new_row < rows as i32 && new_col >= 0 && new_col < cols as i32 {
                let new_pos = (new_row as usize, new_col as usize);
                // check if position is valid and not visited
                if !visited[new_pos.0][new_pos.1] && is_valid_cell(&maze, new_pos) {
                    visited[new_pos.0][new_pos.1] = true;
                    parent.insert(new_pos, current);
                    queue.push_back(new_pos);
                }
            }
        }
    }
    Vec::new()
}

Evrins Hu

evrins

a month ago

4.16ms

89.62kb

use std::collections::HashSet;
pub type Point = (usize, usize);
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let all_paths = find_all_paths(&maze, start, end);
    let mut shortest_length = usize::MAX;
    let mut shortest_path = vec![];
    for path in all_paths {
        if path.len() < shortest_length {
            shortest_length = path.len();
            shortest_path = path;
        }
    }
    shortest_path
}
pub fn find_all_paths(maze: &Vec<Vec<char>>, start: Point, end: Point) -> Vec<Vec<Point>> {
    let mut all_paths: Vec<Vec<Point>> = vec![];
    let mut current_path: Vec<Point> = vec![];
    let mut visited: HashSet<Point> = HashSet::new();
    let m = maze.len();
    if m == 0 {
        return all_paths;
    }
    let n = maze[0].len();
    dfs(
        start,
        end,
        maze,
        m,
        n,
        &mut current_path,
        &mut visited,
        &mut all_paths,
    );
    all_paths
}
pub fn dfs(
    current_pos: Point,
    end: Point,
    maze: &Vec<Vec<char>>,
    m: usize,
    n: usize,
    current_path: &mut Vec<Point>,
    visited: &mut HashSet<Point>,
    all_paths: &mut Vec<Vec<Point>>,
) {
    current_path.push(current_pos);
    visited.insert(current_pos);
    if current_pos == end {
        all_paths.push(current_path.clone());
        visited.remove(&current_pos);
        current_path.pop();
        return;
    }
    for neighbor in neighbors(maze, m, n, current_pos) {
        if visited.contains(&neighbor) {
            continue;
        }
        dfs(neighbor, end, maze, m, n, current_path, visited, all_paths);
    }
    visited.remove(&current_pos);
    current_path.pop();
}
pub fn neighbors(maze: &Vec<Vec<char>>, m: usize, n: usize, point: Point) -> Vec<Point> {
    let i = point.0;
    let j = point.1;
    let directions: Vec<(i32, i32)> = vec![(-1, 0), (1, 0), (0, 1), (0, -1)];
    let mut neighbors: Vec<Point> = Vec::new();
    for d in directions.iter() {
        let (di, dj) = d;
        let (ni, nj) = (i as i32 + di, j as i32 + dj);
        if ni < 0
            || ni >= m as i32
            || nj < 0
            || nj >= n as i32
            || maze[ni as usize][nj as usize] == '#'
        {
            continue;
        }
        neighbors.push((ni as usize, nj as usize));
    }
    neighbors
}

Marco-Normal

a month ago

4.14ms

89.08kb

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![];
    }
    let cols = maze[0].len();
    let mut visited = vec![vec![false; cols]; rows];
    let mut queue: VecDeque<((usize, usize), Vec<(usize, usize)>)> = VecDeque::new();
    visited[start.0][start.1] = true;
    queue.push_back((start, vec![start]));
    // Direction vectors: up, down, left, right
    let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)];
    while let Some(((r, c), path)) = queue.pop_front() {
        // If we reached the end, return the path
        if (r, c) == end {
            return path;
        }
        // Try moving in all four directions
        for (dr, dc) in directions.iter() {
            let nr = r as i32 + dr;
            let nc = c as i32 + dc;
            // Check bounds and valid move
            if nr >= 0 && nc >= 0 && nr < rows as i32 && nc < cols as i32 {
                let (nr, nc) = (nr as usize, nc as usize);
                if !visited[nr][nc] && (maze[nr][nc] == '.' || maze[nr][nc] == 'E') {
                    visited[nr][nc] = true;
                    let mut new_path = path.clone();
                    new_path.push((nr, nc));
                    queue.push_back(((nr, nc), new_path));
                }
            }
        }
    }
    // No path found
    vec![]
}

xxxxsk

a month ago

3.74ms

89.69kb

use std::collections::{VecDeque, HashSet};
pub fn solve_maze(maze: Vec<Vec<char>>, start: (usize, usize), end: (usize, usize)) -> Vec<(usize, usize)> {
    // 边界检查
    if maze.is_empty() || maze[0].is_empty() {
        return vec![];
    }
    let rows = maze.len();
    let cols = maze[0].len();
    // 检查起点和终点是否合法
    if start.0 >= rows || start.1 >= cols || end.0 >= rows || end.1 >= cols {
        return vec![];
    }
    // 方向数组：上、右、下、左
    let directions = [(-1, 0), (0, 1), (1, 0), (0, -1)];
    // 使用队列进行BFS
    let mut queue = VecDeque::new();
    queue.push_back(end);
    // 记录每个点到终点的距离和路径
    let mut distances = vec![vec![None; cols]; rows];
    distances[end.0][end.1] = Some((0, None));
    // 已访问集合
    let mut visited = HashSet::new();
    visited.insert(end);
    while let Some((i, j)) = queue.pop_front() {
        let (current_dist, _) = distances[i][j].unwrap();
        // 检查是否到达起点
        if (i, j) == start {
            break;
        }
        // 遍历四个方向
        for &(di, dj) in &directions {
            let ni = i as isize + di;
            let nj = j as isize + dj;
            // 检查边界
            if ni >= 0 && ni < rows as isize && nj >= 0 && nj < cols as isize {
                let ni = ni as usize;
                let nj = nj as usize;
                // 检查是否可通行且未访问过
                if (maze[ni][nj] == '.' || maze[ni][nj] == 'S') && !visited.contains(&(ni, nj)) {
                    visited.insert((ni, nj));
                    distances[ni][nj] = Some((current_dist + 1, Some((i, j))));
                    queue.push_back((ni, nj));
                }
            }
        }
    }
    // 回溯构建路径
    let mut path = vec![];
    let mut current = start;
    
    // 如果起点没有距离信息，说明不可达
    if distances[current.0][current.1].is_none() {
        return vec![];
    }
    path.push(current);
    
    while current != end {
        if let Some((_, Some((i, j)))) = distances[current.0][current.1] {
            current = (i, j);
            path.push(current);
        } else {
            // 路径中断，返回空
            return vec![];
        }
    }
    path
}

Evgenii Grigorenko

grevgeny

a month ago

4.40ms

89.31kb

use std::collections::{VecDeque, HashMap, HashSet};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut parent_map = HashMap::new();
    let mut visited = HashSet::from([start]);
    let mut queue = VecDeque::from([start]);
    let rows = maze.len() as isize;
    let cols = maze[0].len() as isize;
    while let Some((i, j)) = queue.pop_front() {
        for (di, dj) in [(0, 1), (0, -1), (1, 0), (-1, 0)] {
            let (ni, nj) = (i as isize + di, j as isize + dj);
            if !(0..rows).contains(&ni) || !(0..cols).contains(&nj) {
                continue;
            }
            let pos = (ni as usize, nj as usize);
            if !visited.insert(pos) {
                continue;
            }
            match maze[pos.0][pos.1] {
                'S' | '#' => continue,
                'E' => {
                    parent_map.insert(pos, (i, j));
                    return reconstruct_path(start, end, parent_map).unwrap_or_default();
                },
                '.' => {
                    parent_map.insert(pos, (i, j));
                    queue.push_back(pos)
                },
                _ => panic!("unexpected cell value: {}", maze[pos.0][pos.1]),
            }
        }
    }
    Vec::new()
    
}
fn reconstruct_path(
    start: (usize, usize),
    end: (usize, usize), 
    parent_map: HashMap<(usize, usize), (usize, usize)>
) -> Option<Vec<(usize, usize)>> {
    let mut path = vec![end];
    let mut current = end;
    while current != start {
        current = *parent_map.get(&current)?;
        path.push(current)
    }
    path.reverse();
    Some(path)
}

brucecox01

a month ago

3.87ms

89.63kb

use std::collections::HashMap;
pub enum Direction {
    North,
    South,
    East,
    West,
}
pub fn step(maze: &Vec<Vec<char>>, (x, y): &(usize, usize), dir: &Direction) -> Option<(usize, usize)> {
    let mut x = *x;
    let mut y = *y;
    match *dir {
        Direction::North => {
            if x == 0 { return None }
            x -= 1;
        },
        Direction::South => {
            if x + 1 >= maze.len() { return None }
            x += 1;
        },
        Direction::East => {
            if y + 1 >= maze[x].len() { return None; }
            y += 1;
        },
        Direction::West => {
            if y == 0 { return None; }
            y -= 1;
        },
    }
    if maze[x][y] == '.' || maze[x][y] == 'E' {
        Some ((x, y))
    } else {
        None
    }
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    {
        let (x, y) = start;
        if maze[x][y] != 'S' {
            return vec![];
        }
        let (x, y) = end;
        if maze[x][y] != 'E' {
            return vec![];
        }
    }
    let directions = vec![Direction::North, Direction::South, Direction::East, Direction::West];
    let mut state = HashMap::new();
    let mut todo = vec![start];
    state.insert(start, (0, start));
    while todo.len() > 0 {
        let cur = todo.pop().unwrap();
        // eprintln!("Processing {:?}", cur);
        let (distance, _) = &state.get(&cur).unwrap();
        let distance = distance.clone();
        for dir in &directions {
            if let Some(next) = step(&maze, &cur, dir) {
                match state.get(&next) {
                    Some( (d, _)) if distance >= *d => (),
                    _ => {
                        state.insert(next, (distance + 1, cur));
                        todo.push(next);
                        // eprintln!("Distance to {:?} is {}", next, distance + 1);
                    }
                }
            }
        }
    }
    // eprintln!("Looking for solution to {:?}", end);
    match state.get(&end) {
        None => vec![],
        Some((_, prev)) => {
            let mut revres = vec![end, *prev];
            let mut pos = *prev;
            while pos != start {
                (_, pos) = *state.get(&pos).unwrap();
                revres.push(pos);
            }
            revres.into_iter().rev().collect()
        }
    }
}

Krzysztof Atłasik

katlasik

2 months ago

3.67ms

89.15kb

use std::collections::{HashSet, VecDeque};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut queue = VecDeque::new();
    queue.push_back(vec![start]);
    
    let mut visited = HashSet::new();
    visited.insert(start);
    while let Some(path) = queue.pop_front() {
        if let Some(&(x, y)) = path.last() {
            if (x, y) == end {
                return path
            } else {
                let directions = [
                    (0_isize, 1_isize),  // right
                    (1, 0),  // down
                    (0, -1), // left
                    (-1, 0), // up
                ];
                for (dx, dy) in directions {
                    let new_x = x as isize + dx;
                    let new_y = y as isize + dy;
                    if new_x >= 0 && new_y >= 0 && (new_x as usize) < maze.len() && (new_y as usize) < maze[0].len() {
                        if maze[new_x as usize][new_y as usize] != '#' && !visited.contains(&(new_x as usize, new_y as usize)) {
                            let mut new_path = path.clone();
                            let new_pos = (new_x as usize, new_y as usize);
                            new_path.push(new_pos);
                            queue.push_back(new_path);
                            visited.insert(new_pos);
                        }
                    }
                }
            }
        }
    }
    vec![]
}

ggnne

2 months ago

4.33ms

92.76kb

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.is_empty() {
        return vec![];
    }
    let directions: Vec::<(isize, isize)> = vec![(0, 1), (0, -1), (1, 0), (-1, 0)];
    let mut unvisited: HashSet::<(usize, usize)> = HashSet::new();
    let mut distances: HashMap::<(usize, usize), usize> = HashMap::new();
    let mut paths: HashMap::<(usize, usize), Vec::<(usize, usize)>> = HashMap::new();
    let mut queue: VecDeque::<(usize, usize)> = VecDeque::new();
    for i in 0..maze.len() {
        for j in 0..maze[0].len() {
            if maze[i][j] != '#' {
                distances.insert((i, j), usize::MAX);
                unvisited.insert((i, j));
            }
        }
    }
    distances.insert(start, 0);
    paths.insert(start, vec![]);
        
    queue.push_back(start);
    while !queue.is_empty() {
    
        let curr = queue.pop_front().unwrap();
        unvisited.remove(&curr);
        paths.get_mut(&curr).unwrap().push(curr);
        
        let dist = *distances.get(&curr).unwrap();
        
        for (i, j) in directions.iter() {
            let new = (
                curr.0.checked_add_signed(*i),
                curr.1.checked_add_signed(*j)
            );
            match new {
                (Some(a), Some(b)) if unvisited.contains(&(a, b)) => {
                    let new = (a, b);
                    distances.insert(new, dist + 1);
                    paths.insert(new, paths.get(&curr).unwrap().to_owned());
                    queue.push_back(new);
                }
                _ => ()
            }   
        }
    }
    match paths.get(&end) {
        Some(v) => v.to_owned(),
        None => vec![]
    }
}

Enes

enesscevik

2 months ago

3.64ms

89.26kb

use std::collections::{VecDeque, HashMap};
//// yeniden yazilacak
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![false; cols]; rows];
    let mut parent: HashMap<(usize, usize), (usize, usize)> = HashMap::new();
    let mut queue = VecDeque::new();
    queue.push_back(start);
    visited[start.0][start.1] = true;
    let directions = vec![(0, 1), (1, 0), (0, -1), (-1, 0)];
    while let Some((x, y)) = queue.pop_front() {
        for (dx, dy) in &directions {
            let nx = x as isize + dx;
            let ny = y as isize + dy;
            if nx < 0 || ny < 0 || nx >= rows as isize || ny >= cols as isize {
                continue;
            }
            let (nx, ny) = (nx as usize, ny as usize);
            if visited[nx][ny] || maze[nx][ny] == '#' {
                continue;
            }
            visited[nx][ny] = true;
            parent.insert((nx, ny), (x, y));
            if (nx, ny) == end {
                let mut path = vec![(nx, ny)];
                let mut current = (nx, ny);
                while current != start {
                    current = parent[&current];
                    path.push(current);
                }
                path.reverse();
                return path;
            }
            
            queue.push_back((nx, ny));
        }
    }
    vec![]
}

LeonardoPinheiro23

2 months 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

3 months 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

4 months 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

4 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

4 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

5 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

5 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

5 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

5 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

5 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

5 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

6 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

6 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

6 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

6 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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

7 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
  }
}