AtCoder Beginner Contest 378 D

https://atcoder.jp/contests/abc378/tasks/abc378_d

しらみつぶしでも、元に戻れないので最初以外は行けるところは3通りしかないので、3¹¹ = 177,147、始点が100個以下なので十分に間に合います。今までに行ったことがあるマスはi128を使えば簡単にわかります。

// Count Simple Paths
#![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()
}


//////////////////// Graph ////////////////////

type Node = usize;

struct Graph {
    g: Vec<Vec<Node>>
}

impl Graph {
    fn neighbors((x, y): Point, maze: &Vec<Vec<char>>) -> Vec<Point> {
        let mut points: Vec<Point> = vec![];
        let H = maze.len();
        let W = maze[0].len();
        if x > 0 && maze[x-1][y] == '.' {
            points.push((x - 1, y))
        }
        if x < H - 1 && maze[x+1][y] == '.' {
            points.push((x + 1, y))
        }
        if y > 0 && maze[x][y-1] == '.' {
            points.push((x, y - 1))
        }
        if y < W - 1 && maze[x][y+1] == '.' {
            points.push((x, y + 1))
        }
        points
    }
    
    fn create(maze: Vec<Vec<char>>) -> Graph {
        let H = maze.len();
        let W = maze[0].len();
        let N = H * W;
        let mut g: Vec<Vec<Node>> = vec![vec![]; N];
        for x in 0..H {
            for y in 0..W {
                if maze[x][y] == '#' {
                    continue
                }
                let v = x * W + y;
                for (x1, y1) in Graph::neighbors((x, y), &maze).into_iter() {
                    let v1 = x1 * W + y1;
                    g[v].push(v1)
                }
            }
        }
        Graph { g }
    }
}


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

fn read_input() -> (usize, Vec<Vec<char>>) {
    let v: Vec<usize> = read_vec();
    let (H, K) = (v[0], v[2]);
    let maze: Vec<Vec<char>> =
                (0..H).map(|_| read::<String>().chars().collect::<Vec<_>>()).
                collect();
    (K, maze)
}

type Point = (usize, usize);
// (current node, visited)
type Path = (Node, u128);

fn step(path: Path, graph: &Graph) -> Vec<Path> {
    let mut paths: Vec<Path> = vec![];
    for &v in graph.g[path.0].iter() {
        if ((path.1 >> v) & 1) == 0 {
            let new_path = (v, path.1 | (1 << v));
            paths.push(new_path)
        }
    }
    paths
}

fn F_each(v0: Node, K: usize, graph: &Graph) -> usize {
    let mut paths: Vec<Path> = vec![(v0, 1 << v0)];
    for _ in 0..K {
        let mut new_paths: Vec<Path> = vec![];
        for path in paths.into_iter() {
            let nexts = step(path, graph);
            new_paths.extend(nexts)
        }
        paths = new_paths
    }
    paths.len()
}

fn F(K: usize, maze: Vec<Vec<char>>) -> usize {
    let graph = Graph::create(maze);
    let mut counter: usize = 0;
    for v in 0..graph.g.len() {
        counter += F_each(v, K, &graph)
    }
    counter
}

fn main() {
    let (K, maze) = read_input();
    println!("{}", F(K, maze))
}