752. Open the Lock

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: `'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'`. The wheels can rotate freely and wrap around: for example we can turn `'9'` to be `'0'`, or `'0'` to be `'9'`. Each move consists of turning one wheel one slot.

The lock initially starts at `'0000'`, a string representing the state of the 4 wheels.

You are given a list of `deadends` dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a `target` representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:

```Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".
```

Example 2:

```Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".
```

Example 3:

```Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.
```

Example 4:

```Input: deadends = ["0000"], target = "8888"
Output: -1
```

Constraints:

• `1 <= deadends.length <= 500`
• `deadends[i].length == 4`
• `target.length == 4`
• target will not be in the list `deadends`.
• `target` and `deadends[i]` consist of digits only.

752. Open the Lock
``````struct Solution;
use std::collections::HashSet;

impl Solution {
fn open_lock(deadends: Vec<String>, target: String) -> i32 {
let mut visited: HashSet<u32> = deadends.into_iter().map(Self::s2x).collect();
let target = Self::s2x(target);
let start = 0;
if visited.contains(&start) {
return -1;
}
let mut begin: HashSet<u32> = HashSet::new();
let mut end: HashSet<u32> = HashSet::new();
begin.insert(start);
end.insert(target);
let mut level = 0;
while !begin.is_empty() && !end.is_empty() {
let mut temp: HashSet<u32> = HashSet::new();
for x in begin {
if end.contains(&x) {
return level;
} else {
visited.insert(x);
if !visited.contains(&y) {
temp.insert(y);
}
}
}
}
level += 1;
begin = end;
end = temp
}
-1
}

fn s2x(s: String) -> u32 {
let mut res = 0;
for (i, b) in s.bytes().map(|b| (b - b'0') as u32).enumerate() {
res |= b << (i * 8);
}
res
}

fn x2s(x: u32) -> String {
let mut v: Vec<u8> = vec![0; 4];
for i in 0..4 {
v[i] = ((x >> (i * 8)) & 0xff) as u8;
}
v.into_iter().map(|b| (b + b'0') as char).collect()
}

fn adj(x: u32) -> Vec<u32> {
let mut res = vec![];
for i in 0..4 {
let b1 = (((x >> (i * 8) & 0xff) + 1) % 10) << (i * 8);
let b2 = (((x >> (i * 8) & 0xff) + 9) % 10) << (i * 8);
let mask = !(0xff << (i * 8));