<p>You are given an <code>m x n</code> grid <code>grid</code> where:</p>

<ul>
	<li><code>&#39;.&#39;</code> is an empty cell.</li>
	<li><code>&#39;#&#39;</code> is a wall.</li>
	<li><code>&#39;@&#39;</code> is the starting point.</li>
	<li>Lowercase letters represent keys.</li>
	<li>Uppercase letters represent locks.</li>
</ul>

<p>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.</p>

<p>If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.</p>

<p>For some <code><font face="monospace">1 &lt;= k &lt;= 6</font></code>, there is exactly one lowercase and one uppercase letter of the first <code>k</code> 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.</p>

<p>Return <em>the lowest number of moves to acquire all keys</em>. If it is impossible, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-keys2.jpg" style="width: 404px; height: 245px;" />
<pre>
<strong>Input:</strong> grid = [&quot;@.a..&quot;,&quot;###.#&quot;,&quot;b.A.B&quot;]
<strong>Output:</strong> 8
<strong>Explanation:</strong> Note that the goal is to obtain all the keys not to open all the locks.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-key2.jpg" style="width: 404px; height: 245px;" />
<pre>
<strong>Input:</strong> grid = [&quot;@..aA&quot;,&quot;..B#.&quot;,&quot;....b&quot;]
<strong>Output:</strong> 6
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-keys3.jpg" style="width: 244px; height: 85px;" />
<pre>
<strong>Input:</strong> grid = [&quot;@Aa&quot;]
<strong>Output:</strong> -1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 30</code></li>
	<li><code>grid[i][j]</code> is either an English letter, <code>&#39;.&#39;</code>, <code>&#39;#&#39;</code>, or <code>&#39;@&#39;</code>.&nbsp;</li>
	<li>There is exactly one&nbsp;<code>&#39;@&#39;</code>&nbsp;in the grid.</li>
	<li>The number of keys in the grid is in the range <code>[1, 6]</code>.</li>
	<li>Each key in the grid is <strong>unique</strong>.</li>
	<li>Each key in the grid has a matching lock.</li>
</ul>

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        # BFS
        # Time Complexity: O(m.n.2^k)
        # Space Complexity: O(m.n.2^k)
        # m, n = len(grid), len(grid[0])
        # directions = [[0, -1], [-1, 0], [0, 1], [1, 0]]
        # k = start = 0

        # for i in range(m):
        #     for j in range(n):
        #         if grid[i][j] == '@':
        #             start = [i, j]
        #         elif 'a' <= grid[i][j] <= 'f':
        #             k += 1

        # q = deque([(start[0], start[1], '', '')])
        # visited = set([(start[0], start[1], '', '')])
        # moves = 1
        # while q:
        #     for _ in range(len(q)):
        #         i, j, keys, locks = q.popleft()
        #         for x, y in directions:
        #             i_new, j_new = i + x, j + y
        #             if i_new >= 0 and j_new >= 0 and i_new < m and j_new < n:
        #                 next_cell = grid[i_new][j_new]
        #                 next_state = (i_new, j_new, keys, locks)
        #                 if next_cell == '#' or ('A' <= next_cell <= 'F' and next_cell.lower() not in keys) or next_state in visited:
        #                     continue
        #                 if 'a' <= next_cell <= 'f' and next_cell not in keys:
        #                     if len(keys) == k-1:
        #                         return moves
        #                     next_state = (i_new, j_new, keys + next_cell, locks)
        #                 elif 'A' <= next_cell <= 'F' and next_cell not in locks:
        #                     next_state = (i_new, j_new, keys, locks + next_cell)
        #                 visited.add(next_state)
        #                 q.append(next_state)
        #     moves += 1

        # return -1

        # Bitmask to check for visited
        m, n = len(grid), len(grid[0])
        directions = [[0, -1], [-1, 0], [0, 1], [1, 0]]
        k = start = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    start = [i, j]
                elif 'a' <= grid[i][j] <= 'f':
                    k += 1

        mask = (start[0] * n + start[1])
        get_indices, get_keys, get_locks = (1 << 10) - 1, 63 << 10, 63 << 16
        q = deque([mask])
        visited = set([mask])
        moves = 1
        while q:
            for _ in range(len(q)):
                mask = q.popleft()
                i, j = (mask & get_indices) // n, (mask & get_indices) % n
                keys, locks = mask & get_keys, mask & get_locks
                for x, y in directions:
                    i_new, j_new = i + x, j + y
                    if i_new >= 0 and j_new >= 0 and i_new < m and j_new < n:
                        next_cell = grid[i_new][j_new]
                        next_state = (i_new * n + j_new) | keys | locks
                        if next_cell == '#' or ('A' <= next_cell <= 'F' and not (keys & (1 << (10 + ord(next_cell)-65)))) or next_state in visited:
                            continue
                        if 'a' <= next_cell <= 'f' and not (keys & (1 << (10 + ord(next_cell)-97))):
                            if keys.bit_count() == k-1:
                                return moves
                            next_state = (i_new * n + j_new) | keys | (1 << (10 + ord(next_cell)-97)) | locks
                        elif 'A' <= next_cell <= 'F' and not (locks & (1 << (16 + ord(next_cell)-65))):
                            next_state = (i_new * n + j_new) | keys | locks | (1 << (16 + ord(next_cell)-65))
                        visited.add(next_state)
                        q.append(next_state)
            moves += 1

        return -1
21343