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

Florian Gaudin-Delrieu

FlorianGD

12 days 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

13 days 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

16 days 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

19 days 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

20 days 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

20 days 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

24 days 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

25 days 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

a month 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

a month 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

a month 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

a month 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

a month 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

a month 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

a month 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

a month 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

a month 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

a month 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

a month 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

a month 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

a month ago

4.66ms

89.29kb

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

Markus Bergkvist

mbergkvist

a month ago

7.22ms

89.51kb

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

Kentaro Abe

abekem

a month ago

14.29ms

89.08kb

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

ludovicknecht

a month ago

3.74ms

89.39kb

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

Stefan Roas

sroas

a month ago

4.25ms

88.64kb

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

Masayuki Sunahara

tamanishi

a month ago

3.31ms

88.95kb

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

Ando “Thor” Nando

DivineGod

a month ago

3.54ms

89.19kb

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

James Starkman

jstarkman

a month ago

4.27ms

88.64kb

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

Diego Maia

diegocmsantos

a month ago

5.54ms

89.35kb

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

Jun Huang

leemars

a month ago

4.94ms

89.35kb

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

MichaelScofield

MichaelScofield111

a month ago

3.84ms

89.06kb

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

Elizabeth Doughty

Thymelizabeth

a month ago

4.23ms

89.15kb

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

Sh!n0bu

shinobu52

a month ago

3.58ms

89.06kb

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

0xsmarter

a month ago

3.73ms

89.23kb

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

Andrea Ciprietti

cip999

a month ago

4.67ms

89.23kb

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

senft

a month ago

4.83ms

92.68kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    _end: (usize, usize),
) -> Vec<(usize, usize)> {
    solve_maze_inner(&maze, start, vec![start], vec![])
}
pub fn solve_maze_inner(
    maze: &Vec<Vec<char>>,
    current: (usize, usize),
    path: Vec<(usize, usize)>,
    mut visited: Vec<(usize, usize)>,
) -> Vec<(usize, usize)> {
    let (cur_y, cur_x) = current;
    if maze[cur_y][cur_x] == 'E' {
        return path;
    } else if visited.contains(&current) {
        return vec![];
    } else if maze[cur_y][cur_x] == '#' {
        return vec![];
    }
    visited.push(current);
    let mut paths: Vec<Vec<(usize, usize)>> = vec![];
    if maze[cur_y].len() - 1 > cur_x {
        let step = (cur_y, cur_x + 1);
        let mut new_path = path.clone();
        new_path.push(step);
        paths.push(solve_maze_inner(&maze, step, new_path, visited.clone()));
    }
    if cur_x > 0 {
        let step = (cur_y, cur_x - 1);
        let mut new_path = path.clone();
        new_path.push(step);
        paths.push(solve_maze_inner(&maze, step, new_path, visited.clone()));
    }
    if maze.len() - 1 > cur_y {
        let step = (cur_y + 1, cur_x);
        let mut new_path = path.clone();
        new_path.push(step);
        paths.push(solve_maze_inner(&maze, step, new_path, visited.clone()));
    }
    if cur_y > 0 {
        let step = (cur_y - 1, cur_x);
        let mut new_path = path.clone();
        new_path.push(step);
        paths.push(solve_maze_inner(&maze, step, new_path, visited.clone()));
    }
    paths
        .into_iter()
        .reduce(|a, b| {
            if a.is_empty() {
                b
            } else if b.is_empty() {
                a
            } else if a.len() <= b.len() {
                a
            } else {
                b
            }
        })
        .unwrap()
}

tsuchiya-d

tsucchinoko

a month ago

4.24ms

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::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![]
}

maxvi

a month ago

4.27ms

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::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![]
}

Carsten Cordes

badagent

a month ago

6.17ms

91.49kb

#[derive(Clone, PartialEq, Debug)]
pub struct Pos {
    col: usize,
    row: usize,
}
impl Pos {
    pub fn west(&self, maze: &Maze) -> Option<Self> {
        if self.col == 0 {
            return None;
        }
        let pos = Pos::from((self.col - 1, self.row));
        if maze.is_walkable(&pos) {
            Some(pos)
        } else {
            None
        }
    }
    pub fn east(&self, maze: &Maze) -> Option<Self> {
        let pos = Pos::from((self.col + 1, self.row));
        if maze.is_walkable(&pos) {
            Some(pos)
        } else {
            None
        }
    }
    pub fn north(&self, maze: &Maze) -> Option<Self> {
        if self.row == 0 {
            return None;
        }
        let pos = Pos::from((self.col, self.row - 1));
        if maze.is_walkable(&pos) {
            Some(pos)
        } else {
            None
        }
    }
    pub fn south(&self, maze: &Maze) -> Option<Self> {
        let pos = Pos::from((self.col, self.row + 1));
        if maze.is_walkable(&pos) {
            Some(pos)
        } else {
            None
        }
    }
}
impl From<(usize, usize)> for Pos {
    fn from(source: (usize, usize)) -> Self {
        Self {
            col: source.0,
            row: source.1,
        }
    }
}
pub struct Maze {
    data: Vec<Vec<char>>,
    start: Pos,
    _end: Pos,
    dimensions: (usize, usize),
}
impl Maze {
    pub fn new(data: Vec<Vec<char>>, start: Pos, _end: Pos) -> Result<Self, String> {
        if data.len() < 1 {
            return Err("Illegal Size".into());
        }
        Ok(Self {
            dimensions: (data.len(), data[0].len()),
            data,
            start,
            _end,
        })
    }
    pub fn get_pos(&self, pos: &Pos) -> Option<char> {
        self.data
            .get(pos.row)?
            .get(pos.col)
            .copied()
    }
    pub fn is_walkable(&self, pos: &Pos) -> bool {
        pos.col < self.dimensions.1
            && pos.row < self.dimensions.0
            && self.get_pos(pos).is_some_and(|c| c != '#')
    }
    pub fn is_exit(&self, pos: &Pos) -> bool {
        self.is_walkable(pos) && self.get_pos(pos).is_some_and(|l| l == 'E')
    }
}
pub fn next_step(maze: &Maze, current_pos: Pos, mut path: Vec<Pos>) -> Vec<Vec<Pos>> {
    // Avoid loops
    if path.contains(&current_pos) {
        return vec![];
    }
    if maze.is_exit(&current_pos) {
        println!("Found a way to exit!: {:?}", &current_pos);
        path.push(current_pos);
        return vec![path];
    }
    // Try each direction
    let next_steps: Vec<Pos> = vec![
        current_pos.east(&maze),
        current_pos.west(&maze),
        current_pos.north(&maze),
        current_pos.south(&maze),
    ]
    .into_iter()
    .filter_map(|x| x)
    .collect();
    path.push(current_pos);
    let mut result: Vec<Vec<Pos>> = vec![];
    for next_pos in next_steps {
        let next_paths: Vec<Vec<Pos>> = next_step(maze, next_pos, path.clone())
            .into_iter()
            .filter(|x| x.len() > 0)
            .collect();
        for next_path in next_paths {
            result.push(next_path);
        }
    }
    result
}
pub fn solve_maze(maze: Vec<Vec<char>>, start: (usize, usize), end: (usize, usize)) -> Vec<(usize, usize)> {
    let maze: Maze = Maze::new(maze, start.into(), end.into()).expect("Expected valid grid.");
    let mut paths = next_step(&maze, maze.start.clone(), vec![]);
    println!("Found {} paths.",paths.len());
    paths.sort_by_key(|x| x.len());
    let winner = paths.get(0);
    match winner {
        None => Vec::<(usize, usize)>::new(),
        Some(path) => path.into_iter().map(|x| (x.row, x.col)).collect(),
    }
    // recursively step
}

MichaelScofield

MichaelScofield111

a month ago

3.86ms

89.05kb

use std::collections::{HashMap, VecDeque};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut q = VecDeque::new();
    let mut prev = HashMap::new();
    q.push_front(start);
    prev.insert(start, (usize::MAX, usize::MAX));
    while let Some(pos) = q.pop_back() {
        if pos.0 > 0 {
            let up = (pos.0 - 1, pos.1);
            if !prev.contains_key(&up) && maze[up.0][up.1] != '#' {
                prev.insert(up, pos);
                if up == end {
                    break;
                }
                q.push_front(up);
            }
        }
        if pos.1 < maze[0].len() - 1 {
            let right = (pos.0, pos.1 + 1);
            if !prev.contains_key(&right) && maze[right.0][right.1] != '#' {
                prev.insert(right, pos);
                if right == end {
                    break;
                }
                q.push_front(right);
            }
        }
        if pos.0 < maze.len() - 1 {
            let down = (pos.0 + 1, pos.1);
            if !prev.contains_key(&down) && maze[down.0][down.1] != '#' {
                prev.insert(down, pos);
                if down == end {
                    break;
                }
                q.push_front(down);
            }
        }
        if pos.1 > 0 {
            let left = (pos.0, pos.1 - 1);
            if !prev.contains_key(&left) && maze[left.0][left.1] != '#' {
                prev.insert(left, pos);
                if left == end {
                    break;
                }
                q.push_front(left);
            }
        }
    }
    if !prev.contains_key(&end) {
        return vec![];
    };
    let mut path = Vec::new();
    path.push(end);
    loop {
        let before = prev[&path[path.len() - 1]];
        path.push(before);
        if before == start {
            break;
        }
    }
    path.reverse();
    path
}

Chase Walden

chasewalden

2 months ago

4.25ms

106.49kb

use std::collections::{BinaryHeap, HashMap, hash_map::Entry};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    dbg!(&maze, start, end);
    let maze = Maze::new(maze, start, end);
    let heuristic = |pos| taxicab_distance(pos, end); 
    let mut to_visit = BinaryHeap::from([
        VisitNode::new(start, 0, heuristic),
    ]);
    let mut scores = HashMap::from([
        (start, 0)
    ]);
    let mut previous_pos = HashMap::new();
    while let Some(current) = to_visit.pop() {
        if current.pos == end {
            return reconstruct_path(&previous_pos, end);
        }
        let current_score = scores[&current.pos];
        for neighbor in maze.neighbors(current.pos) {
            let tentative_score = current_score + taxicab_distance(current.pos, neighbor);
            dbg!(neighbor, tentative_score);
            match scores.entry(neighbor) {
                Entry::Occupied(o) if &tentative_score >= o.get() => continue,
                neighbor_score => {
                    previous_pos.insert(neighbor, current.pos);
                    *neighbor_score.or_default() = tentative_score;
                    to_visit.retain(|node| node.pos != neighbor);
                    to_visit.push(
                        VisitNode::new(
                            neighbor, 
                            tentative_score, 
                            heuristic,
                        ),
                    );
                }
            }
        }
    }
    // dead end
    vec![]
}
fn reconstruct_path(
    previous_pos: &HashMap<(usize,usize),(usize, usize)>,
    mut current: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path = vec![current];
    while let Some(&prev) = previous_pos.get(&current) {
        current = prev;
        path.push(current);
    }
    path.reverse();
    path
}
fn taxicab_distance(
    (start_r, start_c): (usize, usize), 
    (end_r, end_c): (usize, usize),
) -> usize {
    // taxi-cab distance
    start_r.abs_diff(end_r) + start_c.abs_diff(end_c)
}
#[derive(Debug,Clone,PartialEq,Eq,Ord)]
struct VisitNode{
    pos: (usize, usize),
    heuristic_score: usize
}
impl VisitNode {
    fn new(
        pos: (usize, usize), 
        score: usize,
        heuristic: impl Fn((usize,usize)) -> usize,
    ) -> Self {
        Self {
            pos,
            heuristic_score: score + heuristic(pos),
        }
    }
}
// impl PartialEq<(usize, usize)> for VisitNode {
//     fn eq(&self, other: &(usize,usize)) -> bool {
//         &self.pos == other
//     }
// }
impl PartialOrd for VisitNode {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.heuristic_score.partial_cmp(&other.heuristic_score)
        .map(|ord| ord.reverse())
    }
}
struct Maze(Vec<Vec<char>>);
impl Maze {
    fn new(
        maze: Vec<Vec<char>>, 
        start: (usize, usize),
        end: (usize, usize),    
    ) -> Self {
        let maze = Self(maze);
        assert_eq!(
            maze.get(start),
            Some('S'),
            "start position doesn't match maze",
        );
        assert_eq!(
            maze.get(end),
            Some('E'),
            "end position doesn't match maze",
        );
        maze
    }
    fn get(&self, (row, col): (usize, usize)) -> Option<char> {
        self.0.get(row)?.get(col).copied()
    }
    fn is_path(&self, pos: (usize, usize)) -> bool {
        !matches!(self.get(pos), None | Some('#'))
    }
    fn neighbors(
        &self, 
        (row, col): (usize, usize),
    ) -> impl Iterator<Item = (usize, usize)> 
    {
        let above = row.checked_sub(1)
            .map(|row| (row, col))
            .filter(|&pos| self.is_path(pos));
        let below = row.checked_add(1)
            .map(|row| (row, col))
            .filter(|&pos| self.is_path(pos));
        let left = col.checked_sub(1)
            .map(|col| (row, col))
            .filter(|&pos| self.is_path(pos));
        let right = col.checked_add(1)
            .map(|col| (row, col))
            .filter(|&pos| self.is_path(pos));
        [above, below, left, right].into_iter().flatten()
    }
}

Andreas

StimhackSoftware

2 months ago

4.27ms

89.48kb


use std::collections::HashMap;
fn neighbor(inp : (usize, usize), max_x : usize, max_y : usize) -> Vec<(usize, usize)> {
    let mut res = Vec::new();
    for (diff_x, diff_y) in [(0, 1), (0, -1), (-1, 0), (1, 0)] {
        let (inp_1i, inp_2i) = (inp.0 as isize, inp.1 as isize);
        let (res_1, res_2) = (inp_1i + diff_x, inp_2i + diff_y);
        if res_1 >= 0 && res_1 < max_x as isize && res_2 >= 0 && res_2 < max_y as isize {
            res.push((res_1 as usize, res_2 as usize))
        }
    }
    res
}
fn reverse_move(passive : HashMap<(usize, usize), (usize, usize)>, last_act : (usize, usize), start : (usize, usize), end : (usize, usize)) -> Vec<(usize, usize)> {
    let mut res = Vec::new();
    let mut cur : (usize, usize) = last_act;
    loop {
        res.push(cur);
        cur = passive.get(&cur).unwrap().clone();
        if cur == start {
            res.push(start);
            let mut pre_end = res.into_iter().rev().collect::<Vec<_>>();
            pre_end.push(end);
            return pre_end
        }
    }
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let max_x = maze.len();
    let max_y = maze[0].len();
    let mut new_active : HashMap<(usize, usize), (usize, usize)> = HashMap::new();
    new_active.insert(start, start);
    let mut active : HashMap<(usize, usize), (usize, usize)> = HashMap::new();
    let mut passive : HashMap<(usize, usize), (usize, usize)> = HashMap::new();
    loop {
        active.clear();
        for (k, v) in new_active.iter() {
            active.insert(k.clone(), v.clone());
        }
        new_active.clear();
        if active.len() == 0 {
            return vec![];
        }
        for (k, v) in active.iter() {
            passive.insert(k.clone(), v.clone());
        }
        for (ux, uy) in active.keys() {
            for (cand_x, cand_y) in neighbor((*ux, *uy), max_x, max_y) {
                if ! passive.contains_key(&(cand_x, cand_y)) {
                    if maze[cand_x][cand_y] == '.' {
                        new_active.insert((cand_x, cand_y), (*ux, *uy));
                    }
                    if maze[cand_x][cand_y] == 'E' {
                        return reverse_move(passive, (*ux, *uy), start, end)
                    }
                }
            }
        }
    }
}

Antoine Cotten

antoineco

2 months ago

3.43ms

89.05kb

use std::collections::{HashMap, VecDeque};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut q = VecDeque::new();
    let mut prev = HashMap::new();
    q.push_front(start);
    prev.insert(start, (usize::MAX, usize::MAX));
    while let Some(pos) = q.pop_back() {
        if pos.0 > 0 {
            let up = (pos.0 - 1, pos.1);
            if !prev.contains_key(&up) && maze[up.0][up.1] != '#' {
                prev.insert(up, pos);
                if up == end {
                    break;
                }
                q.push_front(up);
            }
        }
        if pos.1 < maze[0].len() - 1 {
            let right = (pos.0, pos.1 + 1);
            if !prev.contains_key(&right) && maze[right.0][right.1] != '#' {
                prev.insert(right, pos);
                if right == end {
                    break;
                }
                q.push_front(right);
            }
        }
        if pos.0 < maze.len() - 1 {
            let down = (pos.0 + 1, pos.1);
            if !prev.contains_key(&down) && maze[down.0][down.1] != '#' {
                prev.insert(down, pos);
                if down == end {
                    break;
                }
                q.push_front(down);
            }
        }
        if pos.1 > 0 {
            let left = (pos.0, pos.1 - 1);
            if !prev.contains_key(&left) && maze[left.0][left.1] != '#' {
                prev.insert(left, pos);
                if left == end {
                    break;
                }
                q.push_front(left);
            }
        }
    }
    if !prev.contains_key(&end) {
        return vec![];
    };
    let mut path = Vec::new();
    path.push(end);
    loop {
        let before = prev[&path[path.len() - 1]];
        path.push(before);
        if before == start {
            break;
        }
    }
    path.reverse();
    path
}

Suraj Vijayan

its-me-sv

2 months ago

5.45ms

88.77kb

type Cell = (usize, usize);
pub fn solve_maze(maze: Vec<Vec<char>>, start: Cell, _end: Cell) -> Vec<Cell> {
    solve(&maze, start, &mut vec![]).unwrap_or_default()
}
fn solve(maze: &[Vec<char>], cell: Cell, visited: &mut Vec<Cell>) -> Option<Vec<Cell>> {
    match cell.0 >= maze.len()
        || cell.1 >= maze[0].len()
        || maze[cell.0][cell.1] == '#'
        || visited.contains(&cell)
    {
        true => None,
        false => match maze[cell.0][cell.1] == 'E' {
            true => Some(vec![cell]),
            false => {
                visited.push(cell);
                let neighbors = [
                    (cell.0.wrapping_sub(1), cell.1),
                    (cell.0 + 1, cell.1),
                    (cell.0, cell.1.wrapping_sub(1)),
                    (cell.0, cell.1 + 1),
                ];
                let all_paths = neighbors
                    .into_iter()
                    .map(|neighbor| solve(maze, neighbor, visited))
                    .filter_map(|path| path.is_some().then(|| path.unwrap()))
                    .fold(Vec::new(), |mut paths, mut path| {
                        path.insert(0, cell);
                        paths.push(path);
                        paths
                    });
                visited.pop();
                all_paths.into_iter().min_by_key(|path| path.len())
            }
        },
    }
}

Suraj Vijayan

its-me-sv

2 months ago

3.81ms

88.77kb

type Cell = (usize, usize);
pub fn solve_maze(maze: Vec<Vec<char>>, start: Cell, _end: Cell) -> Vec<Cell> {
    solve(&maze, start, &mut vec![]).unwrap_or_default()
}
fn solve(maze: &[Vec<char>], cell: Cell, visited: &mut Vec<Cell>) -> Option<Vec<Cell>> {
    match cell.0 >= maze.len()
        || cell.1 >= maze[0].len()
        || maze[cell.0][cell.1] == '#'
        || visited.contains(&cell)
    {
        true => None,
        false => match maze[cell.0][cell.1] == 'E' {
            true => Some(vec![cell]),
            false => {
                visited.push(cell);
                let neighbors = [
                    (cell.0.wrapping_sub(1), cell.1),
                    (cell.0 + 1, cell.1),
                    (cell.0, cell.1.wrapping_sub(1)),
                    (cell.0, cell.1 + 1),
                ];
                let all_paths = neighbors
                    .into_iter()
                    .fold(Vec::new(), |mut paths, neighbor| {
                        if let Some(mut path) = solve(maze, neighbor, visited) {
                            path.insert(0, cell);
                            paths.push(path);
                        }
                        paths
                    });
                visited.pop();
                all_paths.into_iter().min_by_key(|path| path.len())
            }
        },
    }
}

René Ribaud

uggla

2 months ago

3.84ms

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)> {
    // Your code here
    let rows = maze.len(); // Y
    let cols = maze[0].len(); // X
    let is_valid = |row: isize, col: isize| -> bool {
        row >= 0
            && col >= 0
            && (row as usize) < rows
            && (col as usize) < cols
            && "SE.".contains(&maze[row as usize][col as usize].to_string())
    };
    let mut visited: HashSet<(usize, usize)> = HashSet::new();
    let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
    let mut predecessors: HashMap<(usize, usize), (usize, usize)> = HashMap::new();
    // Directions for moving in the maze: up, down, left, right
    let directions = [(0, 1), (0, -1), (1, 0), (-1, 0)];
    visited.insert(start);
    queue.push_back(start);
    while let Some(current) = queue.pop_front() {
        // If we reach the end, reconstruct the path
        if current == end {
            let mut path = Vec::new();
            let mut step = end;
            while step != start {
                path.push(step);
                step = predecessors[&step];
            }
            path.push(start); // Add the starting point
            path.reverse(); // Reverse to get the correct order
            return path;
        }
        // Explore neighbors
        for (dr, dc) in directions.iter() {
            let neighbor = (
                (current.0 as isize + dr) as usize,
                (current.1 as isize + dc) as usize,
            );
            if is_valid(neighbor.0 as isize, neighbor.1 as isize) && visited.insert(neighbor) {
                predecessors.insert(neighbor, current);
                queue.push_back(neighbor);
            }
        }
    }
    // If the end is not found
    vec![]
}

Raphael Neider

raneid

2 months ago

4.09ms

99.09kb

use std::collections::{ HashMap, VecDeque };
fn get_field(maze: &Vec<Vec<char>>,
    pos: &(usize, usize)) -> char {
    
    let res = *maze.get(pos.0).unwrap_or(&vec![]).get(pos.1).unwrap_or(&'#');
    println!("  Maze at {:?} is {:?}.", pos, res);
    res
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path: Vec<(usize, usize)> = vec![start];
    if start == end {
        return path;
    }
    let mut todo: VecDeque<(usize, usize)> = VecDeque::new();
    todo.push_back(end);
    let mut dist: HashMap<(usize, usize), usize> = HashMap::new();
    dist.insert(end, 0);
    println!("Maze:\n{:?}", maze);
    while todo.len() > 0 {
        let pos = todo.pop_front().expect("todo list is empty");
        let d = *dist.get(&pos).expect("no distance recorded for position");
        println!("At {pos:?}, distance {d}.");
        if pos.0 > 0 {
            let pn = (pos.0 - 1, pos.1);
            let target = get_field(&maze, &pn);
            if dist.get(&pn).is_none() && target != '#' {
                println!("  Can reach {pn:?} in {} steps.", d + 1);
                dist.insert(pn, d + 1);
                todo.push_back(pn);
            }
        }
        let pn = (pos.0 + 1, pos.1);
        let target = get_field(&maze, &pn);
        if dist.get(&pn).is_none() && target != '#' {
            println!("  Can reach {pn:?} in {} steps.", d + 1);
            dist.insert(pn, d + 1);
            todo.push_back(pn);
        }
        if pos.1 > 0 {
            let pn = (pos.0, pos.1 - 1);
            let target = get_field(&maze, &pn);
            if dist.get(&pn).is_none() && target != '#' {
                println!("  Can reach {pn:?} in {} steps.", d + 1);
                dist.insert(pn, d + 1);
                todo.push_back(pn);
            }
        }
        let pn = (pos.0, pos.1 + 1);
        let target = get_field(&maze, &pn);
        if dist.get(&pn).is_none() && target != '#' {
            println!("  Can reach {pn:?} in {} steps.", d + 1);
            dist.insert(pn, d + 1);
            todo.push_back(pn);
        }
    }
    if dist.get(&start).is_none() {
        println!("Start not reached.");
        return vec![];
    }
    let mut pos = start;
    while pos != end {
        println!("Stepping to {pos:?}.");
        let d = dist.get(&pos).expect("No distance assigned to location");
        if pos.0 > 0 {
            let pn = (pos.0 - 1, pos.1);
            if dist.get(&pn).unwrap_or(&d) < d {
                path.push(pn);
                pos = pn;
                continue;
            }
        }
        let pn = (pos.0 + 1, pos.1);
        if dist.get(&pn).unwrap_or(d) < d {
            path.push(pn);
            pos = pn;
            continue;
        }
        if pos.1 > 0 {
            let pn = (pos.0, pos.1 - 1);
            if dist.get(&pn).unwrap_or(d) < d {
                path.push(pn);
                pos = pn;
                continue;
            }
        }
        let pn = (pos.0, pos.1 + 1);
        if dist.get(&pn).unwrap_or(d) < d {
            path.push(pn);
            pos = pn;
            continue;
        }
    }
    path
}

alemack17

2 months ago

3.89ms

89.60kb

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let max_x=maze[0].len();
    let max_y=maze.len();
    let mut distance=vec![vec![usize::MAX;max_x];max_y];
    let mut visited=vec![vec![false;max_x];max_y];
    let mut previous=vec![vec![None;max_x];max_y];
    for i in 0..maze.len(){
        for j in 0..maze[i].len(){
            if maze[i][j]=='#'{
                visited[i][j]=true;
            }
        }
    }
    
    distance[start.0][start.1]=0;
    previous[start.0][start.1]=Some((0,0));
    while !visited[end.0][end.1]{
        if let Some(next)=find_min_node(&distance,&visited){
            visited[next.0][next.1]=true;
            let new_d=distance[next.0][next.1]+1;
            //right            
            if next.1<max_x-1{
                let x=next.1+1;
                let y=next.0;
                if !visited[y][x] && distance[y][x]>new_d {
                    distance[y][x]=new_d;
                    previous[y][x]=Some(next);
                }
            }
            //left            
            if next.1>0{
                let x=next.1-1;
                let y=next.0;
                if !visited[y][x] && distance[y][x]>new_d{
                    distance[y][x]=new_d;
                    previous[y][x]=Some(next);
                }
            }
            //down  
            if next.0<max_y-1{
                let x=next.1;
                let y=next.0+1;
                if !visited[y][x] && distance[y][x]>new_d {
                    distance[y][x]=new_d;
                    previous[y][x]=Some(next);
                }
            }
            //up 
            if next.0>0{
                let x=next.1;
                let y=next.0-1;
                if !visited[y][x] && distance[y][x]>new_d {
                    distance[y][x]=new_d;
                    previous[y][x]=Some(next);
                }
            }
        }else{
            break;
        }
    }
    let mut solution=vec![];
    if previous[end.0][end.1].is_some(){
        let mut last=end;
        while last!=start{
            solution.push(last);
            last=previous[last.0][last.1].unwrap();
        }
        solution.push(start);
        solution.reverse();
    }
    return solution;  
}
fn find_min_node(distance: &Vec<Vec<usize>>,visited: &Vec<Vec<bool>>)->Option<(usize,usize)>{
    let mut ret=None;
    let mut min=usize::MAX;
    for i in 0..distance.len(){
        for j in 0..distance[i].len(){
            if distance[i][j]<min && !visited[i][j]{
                min=distance[i][j];
                ret=Some((i,j));
            }
        }
    }
    return ret;
}

Ahmad M ElShareif

Ahmah2009

2 months ago

3.74ms

89.01kb

use std::collections::{HashSet, VecDeque};
use std::rc::Rc;
use std::cell::RefCell;
struct PathNode {
    pos: (usize, usize),
    prev: Option<Rc<RefCell<PathNode>>>,
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let (m, n) = (maze.len(), maze[0].len());
    let mut visited = HashSet::new();
    visited.insert(start);
    let mut queue = VecDeque::new();
    queue.push_back(Rc::new(RefCell::new(PathNode { pos: start, prev: None })));
    while let Some(current) = queue.pop_front() {
        let (row, col) = current.borrow().pos;
        if (row, col) == end {
            return reconstruct_path(current);
        }
        for (new_row, new_col) in get_children((row, col), m, n) {
            if !visited.contains(&(new_row, new_col)) && maze[new_row][new_col] != '#' {
                visited.insert((new_row, new_col));
                let new_node = Rc::new(RefCell::new(PathNode {
                    pos: (new_row, new_col),
                    prev: Some(Rc::clone(&current)),
                }));
                queue.push_back(new_node);
            }
        }
    }
    vec![]
}
fn reconstruct_path(end_node: Rc<RefCell<PathNode>>) -> Vec<(usize, usize)> {
    let mut path = Vec::new();
    let mut current = Some(end_node);
    while let Some(node) = current {
        path.push(node.borrow().pos);
        current = node.borrow().prev.clone();
    }
    path.reverse();
    path
}
pub fn get_children(cell: (usize, usize), rows: usize, cols: usize) -> impl Iterator<Item = (usize, usize)> {
    const DIRS: [(i32, i32); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];
    
    DIRS.iter().filter_map(move |&(dx, dy)| {
        let new_row = cell.0 as i32 + dx;
        let new_col = cell.1 as i32 + dy;
        
        if new_row >= 0 && new_col >= 0 && new_row < rows as i32 && new_col < cols as i32 {
            Some((new_row as usize, new_col as usize))
        } else {
            None
        }
    })
}

Ahmad M ElShareif

Ahmah2009

2 months ago

5.24ms

89.20kb

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)> {
    let (m, n) = (maze.len(),maze[0].len());
    let mut visited:HashSet<(usize, usize)> = HashSet::new();
    visited.insert(start);
    let mut queue:VecDeque<(usize, usize, Vec::<(usize, usize)>)> = VecDeque::new();
    queue.push_back((start.0, start.1, vec![]));
    while queue.len() > 0 {
        let (row, col, path) = match queue.pop_front(){
            Some((row,col, path)) => (row,col, path),
            None => return vec![],
        };
        let mut path = path.clone();
        path.push((row,col));
        for child in get_children((row, col), m, n){
            if visited.contains(&child) || maze[child.0][child.1] == '#'{
                continue;
            }
            
            if maze[child.0][child.1] == 'E'{
                path.push(child);
                return path;
            }
            visited.insert(child);
            queue.push_back((child.0, child.1, path.clone()));
        }
    if queue.len() > 5 {
        return vec![];
    }
    }
    return vec![];
}
pub fn get_children(cell:(usize, usize), rows:usize, cols:usize)-> Vec<(usize, usize)> {
    let dirs = vec![(1,0),(0,1),(-1,0),(0,-1)];
    let mut result = vec![];
    for dir in dirs {
        let (row, col) = (cell.0 as i32 + dir.0, cell.1 as i32 + dir.1);
        if row < 0 || col < 0 || row as usize >= rows || col as usize>= cols{
            continue;
        }
        result.push((row as usize, col as usize))
    }
    result
}