AtCoder Beginner Contest 427 E

https://atcoder.jp/contests/abc427/tasks/abc427_e

幅優先探索をすればよいですが、同じ盤面を繰り返すかもしれないので、同じ盤面には移れないように盤面をHashSetのキーにできるようにします。そのためにHashとCloneを実装します。マス目はゴミがあるかどうかだけ分かればいいので1ビットで表されます。1行が12以下なので、8行がu128で表されます。もう4行もu128で表せばよいです（u64でもよいですが）。

// Wind Cleaning
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Grid ////////////////////

use std::collections::HashSet;
use std::hash::{Hash, Hasher};

struct Grid {
    g: Vec<Vec<char>>
}

impl Grid {
    fn H(&self) -> usize {
        self.g.len()
    }
    
    fn W(&self) -> usize {
        self.g[0].len()
    }
    
    fn is_empty(&self) -> bool {
        self.g.iter().all(|row| row.iter().all(|&c| c != '#'))
    }
    
    fn shift(&self, dir: (i32, i32)) -> Option<Grid> {
        let mut g: Vec<Vec<char>> = vec![vec!['.'; self.W()]; self.H()];
        for x in 0..self.H() {
            for y in 0..self.W() {
                if self.g[x][y] == 'T' {
                    g[x][y] = 'T'
                }
                else if self.g[x][y] == '#' {
                    let x1 = (x as i32) + dir.0;
                    let y1 = (y as i32) + dir.1;
                    if x1 < 0 || x1 >= (self.H() as i32) ||
                            y1 < 0 || y1 >= (self.W() as i32) {
                        continue
                    }
                    let c = self.g[x1 as usize][y1 as usize];
                    if c == 'T' {
                        return None
                    }
                    else {
                        g[x1 as usize][y1 as usize] = '#'
                    }
                }
            }
        }
        Some(Grid { g })
    }
    
    fn read() -> Grid {
        let v: Vec<usize> = read_vec();
        let (H, W) = (v[0], v[1]);
        let mut g: Vec<Vec<char>> = vec![vec!['.'; W]; H];
        for x in 0..H {
            let s: String = read();
            for (y, c) in s.chars().enumerate() {
                g[x][y] = c
            }
        }
        Grid { g }
    }
}

impl Hash for Grid {
    fn hash<H: Hasher>(&self, state: &mut H) {
        let mut a: u128 = 0;
        let mut b: u128 = 0;
        for x in 0..self.H() {
            for y in 0..self.W() {
                if self.g[x][y] != '#' {
                    continue
                }
                if x < 8 {
                    a |= 1 << (x * 4 + y)
                }
                else {
                    b |= 1 << ((x - 8) * 4 + y)
                }
            }
        }
        a.hash(state);
        b.hash(state);
    }
}

impl PartialEq for Grid {
    fn eq(&self, other: &Self) -> bool {
        for x in 0..self.H() {
            for y in 0..self.W() {
                if self.g[x][y] != other.g[x][y] {
                    return false
                }
            }
        }
        true
    }
}

impl Eq for Grid {}

impl Clone for Grid {
    fn clone(&self) -> Self {
        let g: Vec<Vec<char>> = self.g.iter().map(|v| v.to_vec()).collect();
        Self { g }
    }
}


//////////////////// process ////////////////////

use std::collections::VecDeque;

fn F(grid: Grid) -> i32 {
    if grid.is_empty() {
        return 0
    }
    
    let mut q: VecDeque<(Grid, i32)> = VecDeque::new();
    q.push_back((grid.clone(), 0));
    let dirs: Vec<(i32, i32)> = vec![(0, 1), (-1, 0), (0, -1), (1, 0)];
    let mut visited: HashSet<Grid> = HashSet::new();
    visited.insert(grid);
    while let Some((g0, n)) = q.pop_front() {
        for &dir in dirs.iter() {
            if let Some(g) = g0.shift(dir) {
                if g.is_empty() {
                    return n + 1
                }
                else if !visited.contains(&g) {
                    visited.insert(g.clone());
                    q.push_back((g, n + 1))
                }
            }
        }
    }
    -1
}

fn main() {
    let grid = Grid::read();
    println!("{}", F(grid))
}