Idiomatic Rust using BFS
Long but idiomatic solution in Rust.\n\n\nuse std::collections::{HashSet, VecDeque};\n\n#[derive(PartialEq, Eq, Hash, Debug, Clone, Copy)]\nenum Tile {\n    Wal
Long but idiomatic solution in Rust.\n\n```\nuse std::collections::{HashSet, VecDeque};\n\n#[derive(PartialEq, Eq, Hash, Debug, Clone, Copy)]\nenum Tile {\n    Wall,\n    Empty,\n}\n\n#[derive(PartialEq, Eq, Hash, Debug, Clone, Copy)]\nstruct Position {\n    i: usize,\n    j: usize,\n}\n\nimpl Position {\n    pub fn new(i: usize, j: usize) -> Position {\n        Position { i, j }\n    }\n\n    pub fn pos_in_dir(&self, d: Direction, grid_sizes: Position) -> Option<Position> {\n        let adj_pos = match d {\n            Direction::Right => Position::new(self.i, self.j + 1),\n            Direction::Left => Position::new(self.i, self.j.checked_sub(1)?),\n            Direction::Down => Position::new(self.i + 1, self.j),\n            Direction::Up => Position::new(self.i.checked_sub(1)?, self.j),\n        };\n\n        if adj_pos.i < grid_sizes.i && adj_pos.j < grid_sizes.j {\n            Some(adj_pos)\n        } else {\n            None\n        }\n    }\n}\n\n#[derive(PartialEq, Eq, Hash, Debug, Clone, Copy)]\nstruct State {\n    box_pos: Position,\n    player_pos: Position,\n}\n\nimpl State {\n    pub fn new(box_pos: Position, player_pos: Position) -> State {\n        State {\n            box_pos,\n            player_pos,\n        }\n    }\n}\n\n#[derive(PartialEq, Eq, Hash, Debug, Clone, Copy)]\nenum Direction {\n    Right,\n    Left,\n    Down,\n    Up,\n}\n\nimpl Direction {\n    pub fn opposite(&self) -> Direction {\n        match self {\n            Direction::Right => Direction::Left,\n            Direction::Left => Direction::Right,\n            Direction::Down => Direction::Up,\n            Direction::Up => Direction::Down,\n        }\n    }\n}\n\nlazy_static! {\n    static ref DIRECTIONS: Vec<Direction> = vec![\n        Direction::Right,\n        Direction::Left,\n        Direction::Down,\n        Direction::Up,\n    ];\n}\n\n/// Returns a list of tuples of `(expected_player_position, moved_box_position)`.\n/// If the player were to reach `expected_player_position`, the box could be moved to `moved_box_position`.\nfn push_positions(grid: &Vec<Vec<Tile>>, box_pos: Position) -> Vec<(Position, Position)> {\n    let mut res = vec![];\n\n    let grid_sizes = Position::new(grid.len(), grid[0].len());\n    for direction in &*DIRECTIONS {\n        let new_player_pos = box_pos.pos_in_dir(direction.opposite(), grid_sizes);\n        let new_box_pos = box_pos.pos_in_dir(*direction, grid_sizes);\n        if let (Some(new_player_pos), Some(new_box_pos)) = (new_player_pos, new_box_pos) {\n            if grid[new_player_pos.i][new_player_pos.j] == Tile::Empty\n                && grid[new_box_pos.i][new_box_pos.j] == Tile::Empty\n            {\n                res.push((new_player_pos, new_box_pos))\n            }\n        }\n    }\n\n    res\n}\n\n/// Returns whether the player can move from `state.player_pos` to `new_player_pos`.\n/// Player cannot move through `Tile::Wall` or `state.box_pos`.\nfn can_move_player(grid: &Vec<Vec<Tile>>, state: State, new_player_pos: Position) -> bool {\n    let mut worklist = vec![state.player_pos];\n\n    let grid_sizes = Position::new(grid.len(), grid[0].len());\n    let mut visited = HashSet::new();\n    visited.insert(state.player_pos);\n    while let Some(player_pos) = worklist.pop() {\n        if player_pos == new_player_pos {\n            return true;\n        }\n\n        for direction in &*DIRECTIONS {\n            if let Some(adj_pos) = player_pos.pos_in_dir(*direction, grid_sizes) {\n                if grid[adj_pos.i][adj_pos.j] == Tile::Empty\n                    && adj_pos != state.box_pos\n                    && visited.insert(adj_pos)\n                {\n                    worklist.push(adj_pos);\n                }\n            }\n        }\n    }\n\n    false\n}\n\n/// Returns the minimum number of pushes to get the box from `start` to `end` given\n/// the player position `player`.\nfn num_pushes(\n    grid: &Vec<Vec<Tile>>,\n    box_pos: Position,\n    end: Position,\n    player_pos: Position,\n) -> Option<usize> {\n    let mut q = VecDeque::new();\n    let init_state = State::new(box_pos, player_pos);\n    q.push_back((0, init_state));\n\n    let mut visited = HashSet::new();\n    visited.insert(init_state);\n    while let Some((cur_dist, state)) = q.pop_front() {\n        if state.box_pos == end {\n            return Some(cur_dist);\n        }\n\n        // let mut s = vec!["".to_string(); grid.len()];\n        // for (i, row) in grid.iter().enumerate() {\n        //     for (j, tile) in row.iter().enumerate() {\n        //         if *tile == Tile::Empty {\n        //             s[i].push(\'.\');\n        //         } else {\n        //             s[i].push(\'#\');\n        //         }\n\n        //         if Position::new(i, j) == state.box_pos {\n        //             s[i].pop();\n        //             s[i].push(\'B\');\n        //         } else if Position::new(i, j) == state.player_pos {\n        //             s[i].pop();\n        //             s[i].push(\'P\');\n        //         }\n        //     }\n        //     println!("{:?}", s[i]);\n        // }\n        // println!("------");\n\n        // For each position the box can be pushed into, check if the player can move behind the box.\n        for (expected_player_pos, new_box_pos) in push_positions(grid, state.box_pos) {\n            let new_state = State::new(new_box_pos, expected_player_pos);\n            // Order is important here! If we insert before moving, we can discount some possibilities early.\n            if can_move_player(grid, state, expected_player_pos) && visited.insert(new_state) {\n                q.push_back((cur_dist + 1, new_state));\n            }\n        }\n    }\n\n    None\n}\n\npub fn min_push_box(grid: Vec<Vec<char>>) -> i32 {\n    let mut box_pos = None;\n    let mut end = None;\n    let mut player_pos = None;\n    let mut grid_tile = vec![vec![]; grid.len()];\n    for (i, row) in grid.into_iter().enumerate() {\n        for (j, ch) in row.into_iter().enumerate() {\n            match &ch {\n                \'#\' => grid_tile[i].push(Tile::Wall),\n                _ => grid_tile[i].push(Tile::Empty),\n            }\n\n            match ch {\n                \'B\' => box_pos = Some(Position::new(i, j)),\n                \'T\' => end = Some(Position::new(i, j)),\n                \'S\' => player_pos = Some(Position::new(i, j)),\n                _ => {}\n            }\n        }\n    }\n\n    match num_pushes(\n        &grid_tile,\n        box_pos.unwrap(),\n        end.unwrap(),\n        player_pos.unwrap(),\n    ) {\n        Some(x) => x as i32,\n        None => -1,\n    }\n}\n\n#[cfg(test)]\nmod test {\n    use super::*;\n\n    #[test]\n    fn test_num_box_pushes() {\n        let grid = vec![\n            vec![\'#\', \'#\', \'#\', \'#\', \'#\', \'#\'],\n            vec![\'#\', \'T\', \'#\', \'#\', \'#\', \'#\'],\n            vec![\'#\', \'.\', \'.\', \'B\', \'.\', \'#\'],\n            vec![\'#\', \'.\', \'#\', \'#\', \'.\', \'#\'],\n            vec![\'#\', \'.\', \'.\', \'.\', \'S\', \'#\'],\n            vec![\'#\', \'#\', \'#\', \'#\', \'#\', \'#\'],\n        ];\n\n        assert_eq!(min_push_box(grid), 3);\n    }\n\n    #[test]\n    fn test_num_box_pushes_five_pushes() {\n        let grid = vec![\n            vec![\'#\', \'#\', \'#\', \'#\', \'#\', \'#\'],\n            vec![\'#\', \'T\', \'.\', \'.\', \'#\', \'#\'],\n            vec![\'#\', \'.\', \'#\', \'B\', \'.\', \'#\'],\n            vec![\'#\', \'.\', \'.\', \'.\', \'.\', \'#\'],\n            vec![\'#\', \'.\', \'.\', \'.\', \'S\', \'#\'],\n            vec![\'#\', \'#\', \'#\', \'#\', \'#\', \'#\'],\n        ];\n\n        assert_eq!(min_push_box(grid), 5);\n    }\n\n    #[test]\n    fn test_num_box_pushes_difficult() {\n        let grid = vec![\n            vec![\'#\', \'.\', \'.\', \'#\', \'T\', \'#\', \'#\', \'#\', \'#\'],\n            vec![\'#\', \'.\', \'.\', \'#\', \'.\', \'#\', \'.\', \'.\', \'#\'],\n            vec![\'#\', \'.\', \'.\', \'#\', \'.\', \'#\', \'B\', \'.\', \'#\'],\n            vec![\'#\', \'.\', \'.\', \'.\', \'.\', \'.\', \'.\', \'.\', \'#\'],\n            vec![\'#\', \'.\', \'.\', \'.\', \'.\', \'#\', \'.\', \'S\', \'#\'],\n            vec![\'#\', \'.\', \'.\', \'#\', \'.\', \'#\', \'#\', \'#\', \'#\'],\n        ];\n\n        assert_eq!(min_push_box(grid), 8);\n    }\n}\n\n```
[]