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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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
}

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

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

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
}

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())
            }
        },
    }
}

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())
            }
        },
    }
}

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

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
}

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

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

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
}

use std::collections::HashSet;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let m = maze.len();
    let n = maze[0].len();
    let mut stack = vec![];
    let mut visited = HashSet::new();
    let mut paths = vec![];
    stack.push((start, vec![]));
    while let Some((point, mut path)) = stack.pop() {
        if point == end {
            path.push(point);
            paths.push(path);
            continue;
        }
        if !visited.insert(point) || maze[point.0][point.1] == '#' {
            continue;
        }
        path.push(point);
        if point.1 < n - 1 {
            stack.push(((point.0, point.1 + 1), path.clone()))
        }
        if point.0 < m - 1 {
            stack.push(((point.0 + 1, point.1), path.clone()))
        }
        if point.1 > 0 {
            stack.push(((point.0, point.1 - 1), path.clone()))
        }
        if point.0 > 0 {
            stack.push(((point.0 - 1, point.1), path.clone()))
        }
    }
    match paths.iter().min_by(|a, b| a.len().cmp(&b.len())) {
        Some(path) => path.to_vec(),
        None => vec![],
    }
}

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 distance = vec![vec![usize::MAX; width]; height];
    distance[start.0][start.1] = 0;
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(start);
    while let Some((y, x)) = queue.pop_front() {
        if (y, x) == end {
            return backtrack_path(&maze, &distance, end);
        }
        for (ny, nx) in get_valid_neighbours(&maze, y, x) {
            if distance[ny][nx] == usize::MAX {
                distance[ny][nx] = distance[y][x] + 1;
                queue.push_back((ny, nx));
            }
        }
    }
    vec![]
}
fn get_valid_neighbours(maze: &[Vec<char>], y: usize, x: usize) -> Vec<(usize, usize)> {
    let height = maze.len();
    let width = maze[0].len();
    let directions = [(0, 1), (1, 0), (0, usize::MAX), (usize::MAX, 0)];
    directions
        .iter()
        .map(|(dy, dx)| (y.wrapping_add(*dy), x.wrapping_add(*dx)))
        .filter(|&(ny, nx)| nx < width && ny < height && maze[ny][nx] != '#')
        .collect()
}
fn backtrack_path(
    maze: &[Vec<char>],
    distance: &[Vec<usize>],
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path = vec![];
    let mut current = end;
    while distance[current.0][current.1] != 0 {
        path.push(current);
        let (y, x) = current;
        for (ny, nx) in get_valid_neighbours(maze, y, x) {
            if distance[ny][nx] == distance[y][x] - 1 {
                current = (ny, nx);
                break;
            }
        }
    }
    path.push(current);
    path.reverse();
    path
}

use std::collections::{HashSet, VecDeque};
type Position = (usize, usize);
type Path = Vec<Position>;
fn get_neighbors(maze: &Vec<Vec<char>>, pos: &(usize, usize)) -> Vec<(usize, usize)> {
    let (row, col) = *pos;
    let rows = maze.len();
    let cols = maze[0].len();
    let mut neighbors = Vec::new();
    let offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]; // Up, Down, Left, Right
    for (row_offset, col_offset) in offsets {
        let new_row = row as isize + row_offset;
        let new_col = col as isize + col_offset;
        if new_row >= 0 && new_row < rows as isize && new_col >= 0 && new_col < cols as isize {
            let new_row = new_row as usize;
            let new_col = new_col as usize;
            if maze[new_row][new_col] != '#' {
                neighbors.push((new_row, new_col));
            }
        }
    }
    neighbors
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut queue: VecDeque<Path> = VecDeque::new();
    queue.push_back(vec![start]);
    let mut visited: HashSet<Position> = HashSet::new();
    visited.insert(start);
    let mut shortest_path: Option<Path> = None;
    let mut min_path_length = usize::MAX;
    while let Some(path) = queue.pop_front() {
        let current_pos = path.last().unwrap();
        if *current_pos == end {
            let path_length = path.len();
            if path_length < min_path_length {
                shortest_path = Some(path.clone());
                min_path_length = path_length;
            }
            continue; // Don't explore further from the end; we already found a shortest path
        }
        for neighbor in get_neighbors(&maze, current_pos) {
            if !visited.contains(&neighbor) {
                visited.insert(neighbor);
                let mut new_path = path.clone();
                new_path.push(neighbor);
                queue.push_back(new_path);
            }
        }
    }
    shortest_path.unwrap_or_default()
}

// https://www.rustfinity.com/practice/rust/challenges/maze-solver/description
use std::cmp::PartialEq;
use std::collections::HashMap;
use std::convert::From;
#[derive(Clone, Default, PartialEq)]
enum Tile {
  #[default]
  Wall,
  OpenPath,
}
type Coord = (usize, usize);
#[derive(Clone, Default)]
struct Coordinate(usize, usize);
impl From<&Coord> for Coordinate {
  fn from(coord: &Coord) -> Self {
    Coordinate(coord.0, coord.1)
  }
}
impl Coordinate {
  fn top(&self) -> Option<Coord> {
    if self.1 > 0 {
      return Option::from((self.0, self.1 - 1));
    }
    None
  }
  fn right(&self) -> Option<Coord> {
    Option::from((self.0 + 1, self.1))
  }
  fn bottom(&self) -> Option<Coord> {
    Option::from((self.0, self.1 + 1))
  }
  fn left(&self) -> Option<Coord> {
    if self.0 > 0 {
      return Option::from((self.0 - 1, self.1));
    }
    None
  }
}
impl PartialEq for Coordinate {
  fn eq(&self, other: &Self) -> bool {
    self.0 == other.0 && self.1 == other.1
  }
}
#[derive(Clone, Default)]
struct CoordHeuristic {
  coord: Coord,
  heuristic_score: Option<i32>,
}
impl CoordHeuristic {
  fn new(coord: Coord) -> Self {
    Self {
      coord,
      heuristic_score: None,
    }
  }
}
#[derive(Clone, Default)]
struct Neighbors {
  top: Option<CoordHeuristic>,
  bottom: Option<CoordHeuristic>,
  right: Option<CoordHeuristic>,
  left: Option<CoordHeuristic>,
}
type NodeMap = HashMap<Coord, Node>;
impl Neighbors {
  fn init(current: Coord) -> Self {
    let init_coord_heuristic = |coord: Option<Coord>| match coord {
      Some(coord) => Option::from(CoordHeuristic::new(coord)),
      None => None,
    };
    let coordinate = Coordinate::from(&current);
    let top = init_coord_heuristic(coordinate.top());
    let right = init_coord_heuristic(coordinate.right());
    let bottom = init_coord_heuristic(coordinate.bottom());
    let left = init_coord_heuristic(coordinate.left());
    Self {
      top,
      right,
      bottom,
      left,
    }
  }
  fn update_coord_heuristic(&mut self, node_map: &HashMap<Coord, Node>) -> &Self {
    let try_update = |ch: &mut Option<CoordHeuristic>| {
      if let Some(ch) = ch {
        if let Some(node) = node_map.get(&ch.coord) {
          if node.tile == Tile::OpenPath {
            ch.heuristic_score = Option::from(node.heuristic_score);
          }
        }
      }
    };
    try_update(&mut self.top);
    try_update(&mut self.right);
    try_update(&mut self.bottom);
    try_update(&mut self.left);
    if self.top.is_some() {
      if self.top.clone().unwrap().heuristic_score.is_none() {
        self.top = None;
      }
    }
    if self.right.is_some() {
      if self.right.clone().unwrap().heuristic_score.is_none() {
        self.right = None;
      }
    }
    if self.bottom.is_some() {
      if self.bottom.clone().unwrap().heuristic_score.is_none() {
        self.bottom = None;
      }
    }
    if self.left.is_some() {
      if self.left.clone().unwrap().heuristic_score.is_none() {
        self.left = None;
      }
    }
    self
  }
}
#[derive(Clone, Default)]
struct Node {
  coordinate: Coordinate,
  neighbors: Neighbors,
  heuristic_score: i32,
  tile: Tile,
  is_visited: bool,
  from: Option<Coord>,
}
impl Node {
  fn calculate_heuristic_score(current: &Coord, end: &Coord) -> i32 {
    i32::abs(end.0 as i32 - current.0 as i32) + i32::abs(end.1 as i32 - current.1 as i32)
  }
  fn init(coord: Coord, tile: Tile, end: &Coord) -> Self {
    Self {
      coordinate: Coordinate::from(&coord),
      neighbors: Neighbors::init(coord),
      heuristic_score: Self::calculate_heuristic_score(&coord, end),
      tile,
      ..Default::default()
    }
  }
  fn mark_as_visited(&mut self) -> &Self {
    self.is_visited = true;
    self
  }
  fn set_from(&mut self, coord: Coord) -> &Self {
    if self.from.is_none() {
      self.from = Option::from(coord);
    }
    self
  }
}
impl PartialEq for Node {
  fn eq(&self, other: &Self) -> bool {
    self.coordinate == other.coordinate
  }
}
#[derive(Debug)]
struct Crawler {
  current_node: Coord,
  nodes_crawled: Vec<Coord>,
}
impl Crawler {
  fn new(current_node: Coord) -> Self {
    Self {
      current_node,
      nodes_crawled: vec![current_node],
    }
  }
  fn crawl(&mut self, node_map: &mut HashMap<Coord, Node>, end: &Coord) -> Vec<Coord> {
    self.nodes_crawled = vec![self.current_node];
    let mut is_dead_end = false;
    loop {
      if is_dead_end {
        self.nodes_crawled.clear();
        break;
      }
      if self.current_node == *end {
        break;
      }
      let mut node = node_map.get(&self.current_node).unwrap().to_owned();
      let mut neighbors: Vec<CoordHeuristic> = Vec::new();
      let mut try_add = |ch: &Option<CoordHeuristic>| {
        if let Some(ch) = ch {
          neighbors.push(ch.clone());
        }
      };
      try_add(&node.neighbors.top);
      try_add(&node.neighbors.right);
      try_add(&node.neighbors.bottom);
      try_add(&node.neighbors.left);
      neighbors.sort_by(|a, b| a.heuristic_score.cmp(&b.heuristic_score));
      let mut i = 0;
      let mut is_forward = false;
      loop {
        if i == neighbors.len() {
          break;
        }
        let mut next_node = node_map.get(&neighbors[i].coord).unwrap().to_owned();
        if !next_node.is_visited {
          is_forward = true;
          node.mark_as_visited();
          node_map.insert(self.current_node, node.to_owned());
          next_node.set_from(self.current_node);
          node_map.insert(neighbors[i].coord, next_node.to_owned());
          self.nodes_crawled.push(neighbors[i].coord);
          self.current_node = neighbors[i].coord;
          break;
        }
        i += 1;
      }
      if !is_forward {
        let prev_coord = node.from;
        if prev_coord.is_some() {
          node.mark_as_visited();
          node_map.insert(self.current_node, node.to_owned());
          self.nodes_crawled.pop();
          self.current_node = prev_coord.unwrap();
        } else {
          is_dead_end = true;
        }
      }
    }
    self.nodes_crawled.clone()
  }
}
struct Maze {
  node_map: NodeMap,
  crawler: Crawler,
  end: Coord,
}
impl Maze {
  fn new(node_map: NodeMap, crawler: Crawler, end: Coord) -> Self {
    Self {
      node_map,
      crawler,
      end,
    }
  }
  fn init(vec: Vec<Vec<char>>, start: Coord, end: Coord) -> Self {
    let mut node_map: NodeMap = HashMap::new();
    let mut x = 0;
    loop {
      if x == vec.len() {
        break;
      }
      let inner_maze = vec.get(x).unwrap();
      let mut y = 0;
      loop {
        if y == inner_maze.len() {
          break;
        }
        let coord = (x, y);
        let tile = match inner_maze.get(y).unwrap() {
          '.' | 'S' | 'E' => Tile::OpenPath,
          _ => Tile::Wall,
        };
        let node = Node::init(coord, tile, &end);
        node_map.insert(coord, node);
        y += 1;
      }
      x += 1;
    }
    let temp_node_map = node_map.clone();
    for m in node_map.iter_mut() {
      m.1.neighbors.update_coord_heuristic(&temp_node_map);
    }
    Self::new(node_map, Crawler::new(start), end)
  }
  fn solve(&mut self) -> Vec<Coord> {
    self.crawler.crawl(&mut self.node_map, &self.end)
  }
}
pub fn solve_maze(maze: Vec<Vec<char>>, start: Coord, end: Coord) -> Vec<Coord> {
  Maze::init(maze, start, end).solve()
}

use std::collections::HashMap;
use std::rc::Rc;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let mut open_list = HashMap::new();
    let mut closed_list = vec![];
    let mut cur_entry = SearchEntry {
        cur_pos: start,
        pre_entry: None,
        f_cost: 0,
        g_cost: 0,
        maze: &maze,
    };
    open_list.insert(start, cur_entry.clone());
    loop {
        if let Some(entry) = open_list.values().min_by_key(|entry| entry.f_cost) {
            cur_entry.update(entry);
        } else {
            return vec![];
        }
        if cur_entry.cur_pos == end {
            break;
        }
        closed_list.push(cur_entry.cur_pos);
        open_list.remove(&cur_entry.cur_pos);
        cur_entry.add_adjacent_positions(end, &mut open_list, &closed_list);
    }
    let mut shortest_path = vec![cur_entry.cur_pos];
    let mut pre_entry = cur_entry.pre_entry;
    while let Some(entry) = &pre_entry {
        shortest_path.push(entry.cur_pos);
        pre_entry = entry.pre_entry.clone();
    }
    shortest_path.reverse();
    shortest_path
}
#[derive(Clone)]
struct SearchEntry<'a> {
    cur_pos: (usize, usize),
    pre_entry: Option<Rc<SearchEntry<'a>>>,
    f_cost: usize,
    g_cost: usize,
    maze: &'a Vec<Vec<char>>,
}
impl<'a> SearchEntry<'a> {
    fn update(&mut self, new: &Self) {
        self.cur_pos = new.cur_pos;
        self.f_cost = new.f_cost;
        self.g_cost = new.g_cost;
        self.pre_entry = if let Some(entry) = &new.pre_entry {
            Some(Rc::clone(entry))
        } else {
            None
        };
    }
    fn get_move_cost(&self, next_pos: (usize, usize)) -> usize {
        if self.cur_pos != next_pos {
            2
        } else {
            1
        }
    }
    fn get_new_position(&self, offset: (isize, isize)) -> Option<(usize, usize)> {
        const WALL: char = '#';
        let (row, col) = (
            self.cur_pos.0 as isize + offset.0,
            self.cur_pos.1 as isize + offset.1,
        );
        if row >= 0
            && (row as usize) < self.maze.len()
            && col >= 0
            && (col as usize) < self.maze[row as usize].len()
            && self.maze[row as usize][col as usize] != WALL
        {
            Some((row as usize, col as usize))
        } else {
            None
        }
    }
    fn get_positiions(&self) -> Vec<(usize, usize)> {
        const OFFSETS: [(isize, isize); 4] = [(-1, 0), (0, -1), (1, 0), (0, 1)];
        let mut pos_list = vec![];
        for &offset in &OFFSETS {
            if let Some(pos) = self.get_new_position(offset) {
                pos_list.push(pos);
            }
        }
        pos_list
    }
    fn add_adjacent_positions(
        &self,
        end: (usize, usize),
        open_list: &mut HashMap<(usize, usize), SearchEntry<'a>>,
        closed_list: &Vec<(usize, usize)>,
    ) {
        for pos in self.get_positiions() {
            if !closed_list.contains(&pos) {
                let h_cost = ((end.0 as isize - pos.0 as isize).abs()
                    + (end.1 as isize - pos.1 as isize).abs())
                    as usize;
                let g_cost = self.g_cost + self.get_move_cost(pos);
                open_list
                    .entry(pos)
                    .and_modify(|e| {
                        if e.g_cost > g_cost {
                            e.g_cost = g_cost;
                            e.f_cost = g_cost + h_cost;
                            e.pre_entry = Some(Rc::new(self.clone()));
                        }
                    })
                    .or_insert_with(|| SearchEntry {
                        cur_pos: pos,
                        pre_entry: Some(Rc::new(self.clone())),
                        f_cost: g_cost + h_cost,
                        g_cost,
                        maze: &self.maze,
                    });
            }
        }
    }
}

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut queue = std::collections::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;
    // Using Breadth-First Search (BFS) algorithm
    while let Some((x, y)) = queue.pop_front() {
        if (x, y) == end {
            let mut path = vec![];
            let mut current = Some((x, y));
            while let Some(pos) = current {
                path.push(pos);
                current = parent[pos.0][pos.1];
            }
            path.reverse();
            return path;
        }
        let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)];
        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;
                parent[nx][ny] = Some((x, y));
            }
        }
    }
    vec![]
}

use std::collections::HashMap;
use std::rc::Rc;
#[derive(PartialEq, Eq, Debug, Hash, Copy, Clone)]
struct Coords(isize, isize); // i,j (row, column)
struct Cell {
    pos:Coords,
    prev:Coords,
    dist:usize
}
impl From<(usize, usize)> for Coords {
    fn from(pos: (usize, usize)) -> Self {
        Coords(pos.0 as isize, pos.1 as isize)
    }
}
impl From<Coords> for (usize, usize) {
    fn from(pos: Coords) -> Self {
        (pos.0 as usize, pos.1 as usize)
    }
}
impl PartialEq for Cell {
    fn eq(&self, other:&Self) -> bool {
        self.pos == other.pos
    }
}
struct Maze<'a> {
    start: Coords,
    end: Coords,
    size: (usize, usize),
    maze: &'a Vec::<Vec::<char>>,
    visited: HashMap::<Coords, Rc<Cell>>,
    queue: Vec::<Rc<Cell>>
}
impl<'a> Maze<'a> {
    fn new(maze:&'a Vec<Vec<char>>, start:Coords, end:Coords) -> Self {
        let size = (maze.len(), if maze.len()>0 {maze[0].len()} else {0});
        Maze{start,
            end,
            maze,
            size,
            visited:HashMap::new(),
            queue:Vec::new()
        }
    }
    fn visit(&mut self, from:Coords, pos:Coords, dist:usize) {
        if pos.0 < 0 || pos.1 < 0 || pos.0 >= self.size.0 as isize || pos.1 >= self.size.1 as isize {
            return;
        }
        if self.maze[pos.0 as usize][pos.1 as usize] == '#' {
            return;
        }
        if let Some(mut e) = self.visited.get_mut(&pos) {
            let em = Rc::get_mut(&mut e).unwrap();
            if em.dist > dist {
                em.dist = dist;
                em.prev = from;
            }
        } else { // newly visited cell
            let new_cell = self.visited.entry(pos).or_insert(Rc::new(Cell{pos, prev:from, dist}));
            self.queue.push(new_cell.clone());
        }
    }
    fn solve(&mut self) -> Option<Vec<(usize, usize)>> {
        self.visit(self.start, self.start, 0);
        while let Some(c) = self.queue.pop() {
            if c.pos == self.end {
                return Some(self.pathTo(&c))
            }
            let new_dist = c.dist+1;            
            self.visit(c.pos, Coords(c.pos.0+1, c.pos.1), new_dist);
            self.visit(c.pos, Coords(c.pos.0-1, c.pos.1), new_dist);
            self.visit(c.pos, Coords(c.pos.0, c.pos.1+1), new_dist);
            self.visit(c.pos, Coords(c.pos.0, c.pos.1-1), new_dist);
            self.queue.sort_by(|a,b| b.dist.cmp(&a.dist));
        }
        None
    }
    fn pathTo(&self, end:&Cell) -> Vec<(usize, usize)> {
        let mut path:Vec::<(usize, usize)> = Vec::new();
        let mut cell:&Cell = &end;
        loop {
            path.push((cell.pos.0 as usize, cell.pos.1 as usize));
            if cell.prev == cell.pos {
                break;
            }
            cell = self.visited.get(&cell.prev).unwrap();
        }
        path.reverse();
        path
    }
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let mut m = Maze::new(&maze, start.into(), end.into());
    m.solve().unwrap_or([].into())
}

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let n_row = maze.len();
    let n_col = maze[0].len();
    if !(start.0 < n_row && start.1 < n_col && end.0 < n_row && end.1 < n_col) {
        return vec![];
    }
    let mut reached = vec![vec![false; n_col]; n_row];
    reached[start.0][start.1] = false;
    let mut nsteps: Vec<Vec<u64>> = vec![vec![1 << 61; n_col]; n_row];
    nsteps[start.0][start.1] = 0;
    let mut queue = VecDeque::new();
    queue.push_back(start);
    let mut path_found = false;
    'done: while let Some(src) = queue.pop_front() {
        let mut dsts = vec![];
        if src.0 > 0 {
            dsts.push((src.0 - 1, src.1))
        }
        if src.0 + 1 < n_row {
            dsts.push((src.0 + 1, src.1))
        }
        if src.1 > 0 {
            dsts.push((src.0, src.1 - 1))
        }
        if src.1 + 1 < n_col {
            dsts.push((src.0, src.1 + 1))
        }
        for dst in dsts {
            if reached[dst.0][dst.1] {
                continue;
            }
            match maze[dst.0][dst.1] {
                '.' => {
                    queue.push_back(dst);
                    reached[dst.0][dst.1] = true;
                    nsteps[dst.0][dst.1] = nsteps[src.0][src.1] + 1;
                }
                'E' => {
                    nsteps[dst.0][dst.1] = nsteps[src.0][src.1] + 1;
                    path_found = true;
                    break 'done;
                }
                _ => {}
            }
        }
    }
    if !path_found {
        return vec![];
    }
    let mut res = vec![end];
    let mut cur = end;
    while cur != start {
        let nstep = nsteps[cur.0][cur.1];
        if cur.0 > 0 && (nstep == nsteps[cur.0 - 1][cur.1] + 1) {
            res.push((cur.0 - 1, cur.1));
            cur = (cur.0 - 1, cur.1)
        } else if cur.0 + 1 < n_row && (nstep == nsteps[cur.0 + 1][cur.1] + 1) {
            res.push((cur.0 + 1, cur.1));
            cur = (cur.0 + 1, cur.1)
        } else if cur.1 > 0 && (nstep == nsteps[cur.0][cur.1 - 1] + 1) {
            res.push((cur.0, cur.1 - 1));
            cur = (cur.0, cur.1 - 1)
        } else {
            res.push((cur.0, cur.1 + 1));
            cur = (cur.0, cur.1 + 1)
        }
    }
    res.reverse();
    res
}

use std::collections::{BinaryHeap, HashMap, HashSet};
use std::cmp::Ordering;
// A* Node
#[derive(Debug, Eq)]
struct Node {
    position: (usize, usize),
    cost: usize, // g: cost from start to current node
    heuristic: usize, // h: estimated cost from current node to end
    total_cost: usize, // f = g + h
}
impl Ord for Node {
    fn cmp(&self, other: &Self) -> Ordering {
        other.total_cost.cmp(&self.total_cost) // **Reverse** for min-heap
    }
}
impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.position == other.position
    }
}
fn manhattan_distance(a: (usize, usize), b: (usize, usize)) -> usize {
    (a.0 as isize - b.0 as isize).abs() as usize + (a.1 as isize - b.1 as isize).abs() as usize
}
fn reconstruct_path(
    came_from: HashMap<(usize, usize), (usize, usize)>,
    mut current: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path = vec![current];
    while let Some(&prev) = came_from.get(&current) {
        current = prev;
        path.push(current);
    }
    path.reverse();
    path
}
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();
    // Priority queue for open set
    let mut open_set = BinaryHeap::new();
    let mut came_from: HashMap<(usize, usize), (usize, usize)> = HashMap::new();
    let mut g_score: HashMap<(usize, usize), usize> = HashMap::new();
    let mut visited: HashSet<(usize, usize)> = HashSet::new();
    // Initialize start node
    open_set.push(Node {
        position: start,
        cost: 0,
        heuristic: manhattan_distance(start, end),
        total_cost: manhattan_distance(start, end),
    });
    g_score.insert(start, 0);
    // Directions for neighbors
    let directions = [(0, 1), (1, 0), (0, usize::MAX), (usize::MAX, 0)];
    while let Some(current) = open_set.pop() {
        if current.position == end {
            return reconstruct_path(came_from, current.position);
        }
        visited.insert(current.position);
        for &(dx, dy) in &directions {
            let neighbor = (
                current.position.0.wrapping_add(dx),
                current.position.1.wrapping_add(dy),
            );
            if neighbor.0 >= rows || neighbor.1 >= cols || visited.contains(&neighbor) {
                continue;
            }
            if maze[neighbor.0][neighbor.1] == '#' {
                continue; // Skip walls
            }
            let tentative_g_score = g_score[&current.position] + 1; // Each step cost = 1
            let is_better_path = tentative_g_score < *g_score.get(&neighbor).unwrap_or(&usize::MAX);
            if is_better_path {
                came_from.insert(neighbor, current.position);
                g_score.insert(neighbor, tentative_g_score);
                open_set.push(Node {
                    position: neighbor,
                    cost: tentative_g_score,
                    heuristic: manhattan_distance(neighbor, end),
                    total_cost: tentative_g_score + manhattan_distance(neighbor, end),
                });
            }
        }
    }
    vec![] // No path found
}

use std::collections::{VecDeque, HashMap};
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::new();
    let mut parents = HashMap::new();
    let mut path = Vec::new();
    visited.push(start);
    queue.push_back(start);
    parents.insert(start, None);
    while let Some(current) = queue.pop_front() {
        if current == end {
            let mut current = Some(end);
            while let Some(point) = current {
                path.push(point);
                current = *parents.get(&point).unwrap();
            }
            path.reverse();
        }
        let neighbors = [
            (current.0.saturating_add(1), current.1),
            (current.0.saturating_sub(1), current.1),
            (current.0, current.1.saturating_add(1)),
            (current.0, current.1.saturating_sub(1)),
        ];
        for neighbor in neighbors {
            if !visited.contains(&neighbor) 
            && maze[current.0][current.1] != '#'
            && neighbor.0 < maze.len() 
            && neighbor.1 < maze[0].len() {
                visited.push(neighbor);
                queue.push_back(neighbor);
                parents.insert(neighbor, Some(current));
            }
        }
    }
    path
}

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    fn solver(pos: (usize, usize), path: &Vec<(usize, usize)>, maze: &Vec<Vec<char>>) -> Option<Vec<(usize,usize)>>{
        // check invalid pos
        let (size0, size1) = (maze.len(), maze[0].len());
        if size0 <= pos.0 || size1 <= pos.1 {return None;}
        if maze[pos.0][pos.1] == '#'        {return None;}
        if path.contains(&pos)              {return None;}
        
        // update path
        let mut path_new = path.to_vec();
        path_new.push(pos);
        // check goal
        if maze[pos.0][pos.1] == 'E' {return Some(path_new);}
        // search
        let mut path_shortest = vec![];
        for pos_new in [
            (pos.0.saturating_add(1), pos.1),
            (pos.0.saturating_sub(1), pos.1),
            (pos.0, pos.1.saturating_add(1)),
            (pos.0, pos.1.saturating_sub(1))
        ] {
            // update path if found shorter one
            if let Some(p) = solver(pos_new, &path_new, &maze) {
                if path_shortest.len() == 0 || p.len() < path_shortest.len(){
                    path_shortest = p;
                }
            }
        }
        if path_shortest.len() != 0 {
            return Some(path_shortest);
        } else {
            return None;
        }
    }
    let path_initial = vec![];
    if let Some(p) = solver(start, &path_initial, &maze) {
        return p;
    } else {
        return vec![];
    }
}

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![false; cols]; rows];
    let mut parent = vec![vec![None; cols]; rows];
    let mut queue = VecDeque::new();
    
    visited[start.0][start.1] = true;
    queue.push_back(start);
    
    while let Some((row, col)) = queue.pop_front() {
        if (row, col) == end {
            return build_path(&parent, start, end);
        }
        
        let moves = [(0, 1), (1, 0), (0, -1), (-1, 0)];
        for (dr, dc) in moves {
            let new_row = row.wrapping_add(dr as usize);
            let new_col = col.wrapping_add(dc as usize);
            
            if new_row < rows && new_col < cols 
                && maze[new_row][new_col] != '#' 
                && !visited[new_row][new_col] {
                visited[new_row][new_col] = true;
                parent[new_row][new_col] = Some((row, col));
                queue.push_back((new_row, new_col));
            }
        }
    }
    
    vec![]
}
fn build_path(
    parent: &Vec<Vec<Option<(usize, usize)>>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path = vec![end];
    let mut current = end;
    
    while current != start {
        if let Some(prev) = parent[current.0][current.1] {
            path.push(prev);
            current = prev;
        }
    }
    
    path.reverse();
    path
}

use std::collections::VecDeque;
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let x_max = maze.len();
    let y_max = maze[0].len();
    let mut queue = VecDeque::new();
    queue.push_back((start.0, start.1, vec![start]));
    let mut visited = vec![];
    enum Dir { U,R,D,L }
    while queue.len() > 0 {
        if let Some((x, y, routes)) = queue.pop_front() {
            if (x, y) == end {
                return routes
            }
            for direction in [Dir::U, Dir::R, Dir::D, Dir::L] {
                let (nx, ny) = match direction {
                    Dir::U => (x, y.wrapping_sub(1)),
                    Dir::R => (x.wrapping_add(1), y),
                    Dir::D => (x, y.wrapping_add(1)),
                    Dir::L => (x.wrapping_sub(1), y),
                };
                if 0 as usize <= nx && nx < x_max
                   && 0 as usize <= ny && ny < y_max
                   && (maze[nx][ny] == '.' || maze[nx][ny] == 'E')
                   && !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![]
}

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 0 as usize <= nx && nx < rows && 0 as usize <= ny && 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![]
}

use std::collections::{VecDeque, HashMap};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    
    let mut return_map = HashMap::new();
    return_map.insert(start, None);
    {
        let mut instruction_queue = VecDeque::new();
        instruction_queue.push_back(start);
        while let Some((x, y)) = instruction_queue.pop_front() {
            let offset = (x+1, y);
            if !return_map.contains_key(&offset) {
                let symbol = maze.get(offset.0)
                    .and_then(|r| r.get(offset.1));
                match symbol {
                    Some('E') => {
                        return_map.insert(offset, Some((x, y)));
                        break;
                    }
                    Some('.') => {
                        return_map.insert(offset, Some((x, y)));
                        instruction_queue.push_back(offset)
                    }
                    _ => {}
                }
            }
            let offset = (x.saturating_sub(1), y);
            if !return_map.contains_key(&offset) {
                let symbol = maze.get(offset.0)
                    .and_then(|r| r.get(offset.1));
                match symbol {
                    Some('E') => {
                        return_map.insert(offset, Some((x, y)));
                        break;
                    }
                    Some('.') => {
                        return_map.insert(offset, Some((x, y)));
                        instruction_queue.push_back(offset)
                    }
                    _ => {}
                }
            }
            let offset = (x, y+1);
            if !return_map.contains_key(&offset) {
                let symbol = maze.get(offset.0)
                    .and_then(|r| r.get(offset.1));
                match symbol {
                    Some('E') => {
                        return_map.insert(offset, Some((x, y)));
                        break;
                    }
                    Some('.') => {
                        return_map.insert(offset, Some((x, y)));
                        instruction_queue.push_back(offset)
                    }
                    _ => {}
                }
            }
            let offset = (x, y.saturating_sub(1));
            if !return_map.contains_key(&offset) {
                let symbol = maze.get(offset.0)
                    .and_then(|r| r.get(offset.1));
                match symbol {
                    Some('E') => {
                        return_map.insert(offset, Some((x, y)));
                        break;
                    }
                    Some('.') => {
                        return_map.insert(offset, Some((x, y)));
                        instruction_queue.push_back(offset)
                    }
                    _ => {}
                }
            }
        }
    }
    let Some(mut prev) = return_map.get(&end).map(|e| *e) else {
        return Vec::new();
    };
    let mut path = VecDeque::new();
    path.push_front(end);
    while let Some(coord) = prev {
        path.push_front(coord);
        prev = return_map[&coord];
    }
    path.into()
}

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Identify maze dimensions
    let rows: usize = maze.len();
    let cols: usize = maze.get(0).expect("Maze needs columns").len();
    // Create helper vectors
    let mut visited: Vec<Vec<bool>> = vec![vec![false; cols]; rows];
    let mut path: Vec<(usize, usize)> = Vec::new();
    // Start dfs search where current node == start
    if dfs(&maze, start, end, &mut path, &mut visited) {
        path
    } else {
        Vec::new()
    }
}
pub fn dfs(
    maze: &Vec<Vec<char>>, 
    current: (usize, usize), 
    end: (usize, usize), 
    path: &mut Vec<(usize, usize)>,
    visited: &mut Vec<Vec<bool>>
) -> bool
{
    // If current == end, add current to path and return true
    let (curr_x, curr_y) = current;
    if current == end {
        path.push(current);
        return true;
    }
    // Check that we are in a valid grid entry
    if curr_x >= maze.len() 
    || curr_y >= maze[0].len() 
    || visited[curr_x][curr_y] == true 
    || maze[curr_x][curr_y] == '#' {
        return false;
    }
    // Mark current grid entry as visited
    visited[curr_x][curr_y] = true;
    // Perform DFS on remaining available locations
    path.push(current);
    for (x, y) in [(1, 0), (0, 1), (usize::MAX, 0), (0, usize::MAX)] {
        let new_x: usize = curr_x.wrapping_add(x);
        let new_y: usize = curr_y.wrapping_add(y);
        if dfs(&maze, (new_x, new_y), end, path, visited) {
            return true;
        }
    }
    // 3. No suitable DFS locations, return false
    path.pop();
    visited[curr_x][curr_y] = false;
    false
}

use std::collections::VecDeque;
#[derive(Clone, Copy, PartialEq)]
enum Direction {
    Up,
    Right,
    Down,
    Left,
}
impl Direction {
    fn get_offset(&self) -> (i32, i32) {
        match self {
            Direction::Up => (-1, 0),
            Direction::Right => (0, 1),
            Direction::Down => (1, 0),
            Direction::Left => (0, -1),
        }
    }
    
    fn all() -> [Direction; 4] {
        [Direction::Up, Direction::Right, Direction::Down, Direction::Left]
    }
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let rows = maze.len();
    if rows == 0 {
        return vec![];
    }
    let cols = maze[0].len();
    
    let mut visited = vec![vec![false; cols]; rows];
    let mut parent = vec![vec![None; cols]; rows];
    let mut queue = VecDeque::new();
    
    queue.push_back(start);
    visited[start.0][start.1] = true;
    
    while let Some(current) = queue.pop_front() {
        if current == end {
            return reconstruct_path(&parent, start, end);
        }
        
        for direction in Direction::all() {
            if let Some(next) = get_next_position(current, direction, rows, cols) {
                if !visited[next.0][next.1] && maze[next.0][next.1] != '#' {
                    visited[next.0][next.1] = true;
                    parent[next.0][next.1] = Some(current);
                    queue.push_back(next);
                }
            }
        }
    }
    
    vec![]
}
fn get_next_position(
    current: (usize, usize),
    direction: Direction,
    rows: usize,
    cols: usize,
) -> Option<(usize, usize)> {
    let (dx, dy) = direction.get_offset();
    let new_x = current.0 as i32 + dx;
    let new_y = current.1 as i32 + dy;
    
    if new_x >= 0 && new_x < rows as i32 && new_y >= 0 && new_y < cols as i32 {
        Some((new_x as usize, new_y as usize))
    } else {
        None
    }
}
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;
    
    path.push(current);
    while current != start {
        if let Some(prev) = parent[current.0][current.1] {
            path.push(prev);
            current = prev;
        } else {
            return vec![];
        }
    }
    
    path.reverse();
    path
}

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path = Vec::new();
    let mut visited = vec![vec![false; maze[0].len()]; maze.len()];
    if dfs(&maze, start, end, &mut path, &mut visited) {
        path
    } else {
        Vec::new()
    }
}
fn dfs(
    maze: &Vec<Vec<char>>,
    current: (usize, usize),
    end: (usize, usize),
    path: &mut Vec<(usize, usize)>,
    visited: &mut Vec<Vec<bool>>,
) -> bool {
    let (x, y) = current;
    if current == end {
        path.push(current);
        return true;
    }
    if x >= maze.len() || y >= maze[0].len() || maze[x][y] == '#' || visited[x][y] {
        return false;
    }
    visited[x][y] = true;
    path.push(current);
    let directions = [(1, 0), (0, 1), (usize::MAX, 0), (0, usize::MAX)];
    for &(dx, dy) in &directions {
        let new_x = x.wrapping_add(dx);
        let new_y = y.wrapping_add(dy);
        if dfs(maze, (new_x, new_y), end, path, visited) {
            return true;
        }
    }
    path.pop();
    visited[x][y] = false;
    false
}

// [down, right, up, left]
const DIRECTONS: [(isize, isize); 4] = [(0, 1), (1, 0), (0, -1), (-1, 0)];
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let rows = maze.len();
    let cols = maze[0].len();
    let mut visited = vec![vec![false; cols]; rows];
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((start, vec![start]));
    visited[start.0][start.1] = true;
    while let Some((current, path)) = queue.pop_front() {
        if current == end {
            return path;
        }
        for (dx, dy) in DIRECTONS.iter() {
            let new_x = current.0 as isize + dx;
            let new_y = current.1 as isize + dy;
            if new_x < 0 || new_x >= rows as isize || new_y < 0 || new_y >= cols as isize {
                continue;
            }
            let new_x = new_x as usize;
            let new_y = new_y as usize;
            if visited[new_x][new_y] || maze[new_x][new_y] == '#' {
                continue;
            }
            let mut new_path = path.clone();
            new_path.push((new_x, new_y));
            queue.push_back(((new_x, new_y), new_path));
            visited[new_x][new_y] = true;
        }
    }
    Vec::new()
}

use std::collections::{VecDeque, HashSet, HashMap};
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let rows = maze.len();
    let cols = maze[0].len();
    let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)];
    let mut queue = VecDeque::new();
    let mut visited = HashSet::new();
    let mut came_from = HashMap::new();
    queue.push_back(start);
    visited.insert(start);
    while let Some((x, y)) = queue.pop_front() {
        if (x, y) == end {
            return reconstruct_path(came_from, start, end);
        }
        for (dx, dy) in directions.iter() {
            let nx = x as isize + dx;
            let ny = y as isize + dy;
            if nx >= 0 && nx < rows as isize && ny >= 0 && ny < cols as isize {
                let nx = nx as usize;
                let ny = ny as usize;
                if maze[nx][ny] != '#' && !visited.contains(&(nx, ny)) {
                    queue.push_back((nx, ny));
                    visited.insert((nx, ny));
                    came_from.insert((nx, ny), (x, y));
                }
            }
        }
    }
    Vec::new()
}
fn reconstruct_path(
    came_from: 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 = came_from[&current];
    }
    path.push(start);
    path.reverse();
    path
}

use std::collections::VecDeque;
#[derive(Clone, Copy, PartialEq)]
enum Direction {
    Up,
    Right,
    Down,
    Left,
}
impl Direction {
    fn get_offset(&self) -> (i32, i32) {
        match self {
            Direction::Up => (-1, 0),
            Direction::Right => (0, 1),
            Direction::Down => (1, 0),
            Direction::Left => (0, -1),
        }
    }
    
    fn all() -> [Direction; 4] {
        [Direction::Up, Direction::Right, Direction::Down, Direction::Left]
    }
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let rows = maze.len();
    if rows == 0 {
        return vec![];
    }
    let cols = maze[0].len();
    
    // Create visited array and parent tracking for path reconstruction
    let mut visited = vec![vec![false; cols]; rows];
    let mut parent = vec![vec![None; cols]; rows];
    let mut queue = VecDeque::new();
    
    // Start BFS
    queue.push_back(start);
    visited[start.0][start.1] = true;
    
    // BFS until we find the end or exhaust all possibilities
    while let Some(current) = queue.pop_front() {
        if current == end {
            return reconstruct_path(&parent, start, end);
        }
        
        for direction in Direction::all() {
            if let Some(next) = get_next_position(current, direction, rows, cols) {
                // Check if the next position is valid and unvisited
                if !visited[next.0][next.1] && maze[next.0][next.1] != '#' {
                    visited[next.0][next.1] = true;
                    parent[next.0][next.1] = Some(current);
                    queue.push_back(next);
                }
            }
        }
    }
    
    // No path found
    vec![]
}
fn get_next_position(
    current: (usize, usize),
    direction: Direction,
    rows: usize,
    cols: usize,
) -> Option<(usize, usize)> {
    let (dx, dy) = direction.get_offset();
    let new_x = current.0 as i32 + dx;
    let new_y = current.1 as i32 + dy;
    
    if new_x >= 0 && new_x < rows as i32 && new_y >= 0 && new_y < cols as i32 {
        Some((new_x as usize, new_y as usize))
    } else {
        None
    }
}
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;
    
    path.push(current);
    while current != start {
        if let Some(prev) = parent[current.0][current.1] {
            path.push(prev);
            current = prev;
        } else {
            return vec![]; // This shouldn't happen if we found a path
        }
    }
    
    path.reverse();
    path
}

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path = Vec::new();
    let mut visited = vec![vec![false; maze[0].len()]; maze.len()];
    if dfs(&maze, start, end, &mut path, &mut visited) {
        path
    } else {
        Vec::new()
    }
}
fn dfs(
    maze: &Vec<Vec<char>>,
    current: (usize, usize),
    end: (usize, usize),
    path: &mut Vec<(usize, usize)>,
    visited: &mut Vec<Vec<bool>>,
) -> bool {
    let (x, y) = current;
    if current == end {
        path.push(current);
        return true;
    }
    if x >= maze.len() || y >= maze[0].len() || maze[x][y] == '#' || visited[x][y] {
        return false;
    }
    visited[x][y] = true;
    path.push(current);
    let directions = [(1, 0), (0, 1), (usize::MAX, 0), (0, usize::MAX)];
    for &(dx, dy) in &directions {
        let new_x = x.wrapping_add(dx);
        let new_y = y.wrapping_add(dy);
        if dfs(maze, (new_x, new_y), end, path, visited) {
            return true;
        }
    }
    path.pop();
    visited[x][y] = false;
    false
}

use std::collections::HashSet;
pub fn neighbours(point: (usize, usize),h:usize,w:usize) -> Vec<(usize, usize)> {
    let mut neighbours = vec![];
    if point.0 > 0 {
        neighbours.push((point.0 - 1 , point.1));
    }
    if point.1 > 0 {
        neighbours.push((point.0 , point.1 - 1));
    }
    if point.0 < h - 1 {
        neighbours.push((point.0 + 1 , point.1));
    }
    if point.1 < w - 1 {
        neighbours.push((point.0, point.1 + 1));
    }
    neighbours
}
pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    let mut path = vec![start];
    let mut checked = HashSet::<(usize, usize)>::new();
    let h = maze.len(); 
    let w = maze[0].len();
    while path.len() != 0 {
        let current = path[path.len() - 1];
        checked.insert(current);
        for n in neighbours(current, h, w) {
            if !checked.contains(&n) {
                let v = maze[n.0][n.1];
                if v == '#'{
                    checked.insert(n);
                }else{
                    path.push(n);
                    if end == n {
                        return path;
                    }
                    break;
                }
            }
        }
        if checked.contains(&path[path.len() - 1]){
            path.pop();
        }
    }
    path
}