Shortest path to get all keys

/*
 * You are given an m x n grid grid where:
 * '.' is an empty cell.
 * '#' is a wall.
 * '@' is the starting point.
 * Lowercase letters represent keys.
 * Uppercase letters represent locks.
 * 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.
 * If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.
 * For some 1 <= k <= 6, 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.
 * Return the lowest number of moves to acquire all keys. If it is impossible, return -1.
 * Example 1:
 * Input: grid = ["@.a..","###.#","b.A.B"]
 * Output: 8
 * Explanation: Note that the goal is to obtain all the keys not to open all the locks.
 * Example 2:
 * Input: grid = ["@..aA","..B#.","....b"]
 * Output: 6
 * Example 3:
 * Input: grid = ["@Aa"]
 * Output: -1
 * Constraints:
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 30
 * grid[i][j] is either an English letter, '.', '#', or '@'.
 * There is exactly one '@' in the grid.
 * The number of keys in the grid is in the range [1, 6].
 * Each key in the grid is unique.
 * Each key in the grid has a matching lock.
 */

use std::collections::VecDeque;
impl Solution {
  pub fn shortest_path_all_keys(grid: Vec<String>) -> i32 {
    let grid: Vec<Vec<u8>> = grid.iter().map(|s| s.bytes().collect()).collect();
    let m = grid.len();
    let n = grid[0].len();
    let mut start = (0usize, 0usize);
    let mut all_keys = 0i32;
    for i in 0..m {
      for j in 0..n {
        match grid[i][j] {
          b'@' => start = (i, j),
          b'a'..=b'f' => all_keys |= 1 << (grid[i][j] - b'a'),
          _ => {}
        }
      }
    }
    let mut visited = vec![vec![vec![false; 1 << 6]; n]; m];
    let mut queue = VecDeque::new();
    queue.push_back((start.0, start.1, 0i32, 0i32));
    visited[start.0][start.1][0] = true;
    while let Some((r, c, keys, dist)) = queue.pop_front() {
      for &(dr, dc) in &[(-1i32,0i32),(1,0),(0,-1),(0,1)] {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr < 0 || nc < 0 || nr >= m as i32 || nc >= n as i32 { continue; }
        let (nr, nc) = (nr as usize, nc as usize);
        let cell = grid[nr][nc];
        if cell == b'#' { continue; }
        // Check if locked door
        if cell >= b'A' && cell <= b'F' {
          if keys & (1 << (cell - b'A')) == 0 { continue; }
        }
        let mut new_keys = keys;
        if cell >= b'a' && cell <= b'f' {
          new_keys |= 1 << (cell - b'a');
        }
        if new_keys == all_keys { return dist + 1; }
        if !visited[nr][nc][new_keys as usize] {
          visited[nr][nc][new_keys as usize] = true;
          queue.push_back((nr, nc, new_keys, dist + 1));
        }
      }
    }
    -1
  }
}