-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.rs
72 lines (60 loc) · 1.81 KB
/
main.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
use std::{
collections::{HashMap, HashSet},
io::{self, BufRead},
};
type Node = String;
type Path = Vec<Node>;
struct Map(HashMap<Node, HashSet<Node>>);
impl Map {
pub fn new() -> Self {
Self(HashMap::new())
}
fn add_single_edge(&mut self, n1: &Node, n2: &Node) {
if !self.0.contains_key(n1) {
self.0.insert(n1.clone(), HashSet::new());
};
let vec = self.0.get_mut(n1).unwrap();
vec.insert(n2.clone());
}
pub fn add_edge(&mut self, n1: &Node, n2: &Node) {
self.add_single_edge(n1, n2);
self.add_single_edge(n2, n1);
}
pub fn get_next_node(&self, node: &Node) -> Vec<&Node> {
let next_nodes = self.0.get(node);
match next_nodes {
Some(set) => set.iter().collect(),
None => vec![],
}
}
}
fn visit(path: &Path, map: &Map) -> Vec<Path> {
let mut paths: Vec<Path> = vec![];
let current_node = path.last().unwrap();
if current_node == "end" {
paths.push(path.clone());
return paths;
}
for next_node in map.get_next_node(current_node) {
if next_node.chars().next().unwrap().is_lowercase() && path.contains(next_node) {
continue;
}
let mut next_path = path.clone();
next_path.push(next_node.clone());
let mut found_paths = visit(&next_path, map);
paths.append(&mut found_paths);
}
paths
}
fn main() {
let stdin = io::stdin();
let lines = stdin.lock().lines();
let mut map = Map::new();
for _line in lines {
let line = _line.unwrap();
let splited = line.split("-").collect::<Vec<&str>>();
map.add_edge(&splited[0].to_owned(), &splited[1].to_owned());
}
let paths = visit(&vec!["start".to_owned()], &map);
println!("ans {}", paths.len());
}