<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>

def neighbors(grid, r, c):
    H, W = len(grid), len(grid[0])
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr = r + dr
        nc = c + dc
        if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] != '#':
            yield nr, nc

def locations(grid):
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] not in "#.":
                yield r, c

def targets_and_num_keys(grid):
    result = "".join(grid).replace("#", "").replace(".", "")    
    return result, (len(result) - 1) // 2

def bfs(grid, loc, targets, keys=None):
    q = deque([(0, loc)])
    visited = set([loc])
    result = defaultdict(lambda: -1)

    while q:
        distance, curr = q.pop()
        r, c = curr
        cell = grid[r][c]
        
        if cell in targets:
            result[cell] = distance
        
        for succ in neighbors(grid, r, c):
            nr, nc = succ
            cell = grid[nr][nc]

            if cell.isupper() and (not keys or cell.lower() not in keys):
                result[cell] = min(result.get(cell, float('inf')), distance + 1)
                continue

            if succ not in visited:
                q.appendleft((distance + 1, succ))
                visited.add(succ)

    return result

def djikstra(graph, loc, state, desired_state):
    distances = defaultdict(lambda: float('inf'))
    distances[loc, state] = 0
    q = [(0, loc, state)]
    visited = set([])

    while q:
        distance, curr, state = heapq.heappop(q)
        if state == desired_state: return distance
        visited.add((curr, state))

        if distance < distances[curr, state]:
            distances[curr, state] = distance
        
        for succ, weight in graph[curr].items():
            if succ.isupper() and not (state & (1 << (ord(succ.lower()) - ord('a')))):
                continue

            new_state = state
            if succ.islower():
                new_state |= (1 << (ord(succ) - ord('a')))
            
            if (succ, new_state) in visited: continue

            if distance + weight < distances[succ, new_state]:
                distances[succ] = distance + weight
                heapq.heappush(q, (distance + weight, succ, new_state))

    return -1


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        targets, key_count = targets_and_num_keys(grid)
        graph = {}

        for r, c in locations(grid):
            cell = grid[r][c]
            distances = bfs(grid, (r, c), targets)
            del distances[cell]
            graph[cell] = distances

        desired_state = (1 << key_count) - 1
        return djikstra(graph, '@', 0, desired_state)
17893