864. Shortest Path to Get All Keys Hard

1/**
2 * [864] Shortest Path to Get All Keys
3 *
4 * You are given an m x n grid grid where:
5 * 
6 * 	'.' is an empty cell.
7 * 	'#' is a wall.
8 * 	'@' is the starting point.
9 * 	Lowercase letters represent keys.
10 * 	Uppercase letters represent locks.
11 * 
12 * You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall.
13 * If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.
14 * For some <font face="monospace">1 <= k <= 6</font>, there is exactly one lowercase and one uppercase letter of the first k letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.
15 * Return the lowest number of moves to acquire all keys. If it is impossible, return -1.
16 *  
17 * Example 1:
18 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-keys2.jpg" style="width: 404px; height: 245px;" />
19 * Input: grid = ["@.a..","###.#","b.A.B"]
20 * Output: 8
21 * Explanation: Note that the goal is to obtain all the keys not to open all the locks.
22 * 
23 * Example 2:
24 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-key2.jpg" style="width: 404px; height: 245px;" />
25 * Input: grid = ["@..aA","..B#.","....b"]
26 * Output: 6
27 * 
28 * Example 3:
29 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-keys3.jpg" style="width: 244px; height: 85px;" />
30 * Input: grid = ["@Aa"]
31 * Output: -1
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	m == grid.length
37 * 	n == grid[i].length
38 * 	1 <= m, n <= 30
39 * 	grid[i][j] is either an English letter, '.', '#', or '@'.
40 * 	The number of keys in the grid is in the range [1, 6].
41 * 	Each key in the grid is unique.
42 * 	Each key in the grid has a matching lock.
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/shortest-path-to-get-all-keys/
48// discuss: https://leetcode.com/problems/shortest-path-to-get-all-keys/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn shortest_path_all_keys(grid: Vec<String>) -> i32 {
54        0
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_864() {
66    }
67}
68