We are given a 2-dimensional grid. "." is an empty cell, "#" is a wall, "@" is the starting point, ("a", "b", ...) are keys, and ("A", "B", ...) are locks.
We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions.  We cannot walk outside the grid, or walk into a wall.  If we walk over a key, we pick it up.  We can't walk over a lock unless we have the 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's impossible, return -1.
 

Example 1:
Input: ["@.a.#","###.#","b.A.B"]
Output: 8


Example 2:
Input: ["@..aA","..B#.","....b"]
Output: 6


 
Note:

1 <= grid.length <= 30
1 <= grid[0].length <= 30
grid[i][j] contains only '.', '#', '@', 'a'-'f' and 'A'-'F'
The number of keys is in [1, 6].  Each key has a different letter and opens exactly one lock.

Difficulty: interview

Starter code:

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        

Solutions:
import heapq
from collections import deque, defaultdict
class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m,n = len(grid),len(grid[0])
        key_lock_loc = {ch:(i,j) for i,row in enumerate(grid) for j,ch in enumerate(row) if ch not in {'.','#'}}
        key_cnt = sum(key_lock in ('a','b','c','d','e','f')for key_lock in key_lock_loc)
        
        def bfs_from(src):
            i,j = key_lock_loc[src]
            seen = defaultdict(lambda: False)
            seen[i,j] = True
            # only locations which are not wall will be put into the queue
            dque = deque([(i,j,0)]) 
            dist = {}
            while dque:
                i,j,d = dque.popleft()
                ch = grid[i][j]
                if ch != src and ch != '.': # reaches lock or key
                    dist[ch] = d
                    continue
                # '#' or '.'
                for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                    if not (0<=x<m and 0<=y<n) or grid[x][y] == '#' or seen[x,y]:
                        continue
                    seen[x,y] = True
                    dque.append((x,y,d+1))
            return dist
        
        dists = {key_lock:bfs_from(key_lock) for key_lock in key_lock_loc}
        all_keys_bitmap = 2 ** key_cnt -1
        
        hq = [(0,'@',0)]
        final_dist = defaultdict(lambda: float('inf'))
        final_dist['@', 0] = 0
        while hq:
            d,ch,keys_bitmap = heapq.heappop(hq)
            if final_dist[ch,keys_bitmap] < d:
                continue
            if keys_bitmap == all_keys_bitmap:
                return d
            for next_key_lock, d2 in list(dists[ch].items()):
                keys_bitmap2 = keys_bitmap
                if next_key_lock.islower(): # key
                    keys_bitmap2 |= (1 <<(ord(next_key_lock) - ord('a')))
                elif next_key_lock.isupper(): # ch
                    if not(keys_bitmap &(1 <<(ord(next_key_lock) - ord('A')))):
                        continue
                if d + d2 < final_dist[next_key_lock, keys_bitmap2]:
                    final_dist[next_key_lock, keys_bitmap2]= d + d2
                    heapq.heappush(hq,(d+d2,next_key_lock,keys_bitmap2))
        return -1
        
                    


class Solution:
    def shortestPathAllKeys(self, grid) -> int:
        from collections import deque
        import copy
        rows = len(grid)
        if rows == 0:
            return 0
        cols = len(grid[0])
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        num_keys = 0
        start = [-1, -1]
        for i in range(rows):
            for j in range(cols):
                ch = grid[i][j]
                if 0 <= ord(ch) - ord('a') <= 5:
                    num_keys += 1
                if ch == '@':
                    start[0] = i
                    start[1] = j
        curr_level = deque()
        next_level = deque()
        visited = set()
        visited.add((0, start[0], start[1]))
        curr_level.append((0, start[0], start[1]))
        steps = 0
        while len(curr_level) > 0:
            for i in range(len(curr_level)):
                ori_keys, x, y = curr_level.popleft()
                for d in dirs:
                    keys = ori_keys
                    new_x = x + d[0]
                    new_y = y + d[1]
                    if new_x < 0 or new_x >= rows or new_y < 0 or new_y >= cols:
                        continue
                    ch = grid[new_x][new_y]
                    if ch == '#':
                        continue
                    ascii_minus_lower = ord(ch) - ord('a')
                    ascii_minus_upper = ord(ch) - ord('A')
                    if 0 <= ascii_minus_lower <= 5:
                        keys |= (1 << ascii_minus_lower)
                        if keys == ((1 << num_keys) - 1):
                            return steps + 1
                    if 0 <= ascii_minus_upper <= 5 and (((keys >> ascii_minus_upper) & 1) == 0):
                        continue
                    if (keys, new_x, new_y) not in visited:
                        visited.add((keys, new_x, new_y))
                        next_level.append((keys, new_x, new_y))
            curr_level = copy.deepcopy(next_level)
            next_level.clear()
            steps += 1
        return -1
                    
                            
                    
                
        
                    
        


class Solution:
    def __init__(self):
        self.DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        start_x, start_y = -1, -1
        target_keys = 0
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    start_x, start_y = i, j
                # elif grid[i][j].islower():
                elif grid[i][j] in 'abcdef':
                    target_keys |= 1 << (ord(grid[i][j]) - ord('a'))
                    # final_keys <<= 1
                    # final_keys |= 1
        
        pq = [(0, 0, start_x, start_y)]
        visited = set((0, start_x, start_y))

        while pq:
            curr_steps, curr_keys, x, y = heapq.heappop(pq)

            if curr_keys == target_keys:
                return curr_steps

            for delta_x, delta_y in self.DIR:
                next_x, next_y = x + delta_x, y + delta_y

                if not self.inbound(grid, next_x, next_y) or grid[next_x][next_y] == '#':
                    continue

                if grid[next_x][next_y] in 'ABCDEF':
                    if (curr_keys >> (ord(grid[next_x][next_y]) - ord('A'))) & 1:
                        next_keys = curr_keys
                    else:
                        continue
                elif grid[next_x][next_y] in 'abcdef':
                    next_keys = curr_keys | (1 << (ord(grid[next_x][next_y]) - ord('a')))
                else: # the next location is @ or .
                    next_keys = curr_keys

                if (next_keys, next_x, next_y) in visited:
                        continue

                heapq.heappush(pq, (curr_steps + 1, next_keys, next_x, next_y))
                visited.add((next_keys, next_x, next_y))
        return -1
                
    def inbound(self, grid, x, y):
        return 0 <= x < len(grid) and 0 <= y < len(grid[0])

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m=len(grid)
        n=len(grid[0])
        
        # handles neighbor, returns neighbor next state
        def neighbor(i,j, keys):
            keys_list = list(keys)
            if grid[i][j] in ['.', '@']:
                return (i,j,keys)
            elif grid[i][j].islower():
                if grid[i][j] in keys_list: # already picked key, treat as empty cell
                    return (i,j,keys)
                else: # pick up new key
                    keys_list.append(grid[i][j])
                    new_keys=''.join(keys_list)
                    return (i,j,new_keys)
            elif grid[i][j].isupper():
                if grid[i][j].lower() in keys_list: # treat lock as empty cell if have the key
                    return (i,j,keys)
            return None
        
        def move(i,j,keys):
            nexts=[]
            if i>0:
                nei = neighbor(i-1,j,keys)
                if nei:
                    nexts.append(nei)
            if i<m-1:
                nei=neighbor(i+1,j,keys)
                if nei:
                    nexts.append(nei)
            if j>0:
                nei=neighbor(i,j-1,keys)
                if nei:
                    nexts.append(nei)
            if j<n-1:
                nei= neighbor(i,j+1,keys)
                if nei:
                    nexts.append(nei)
            return nexts
                  
        def get_start_and_keys():
            x, y, keys = -1, -1, 0
            for i in range(m):
                for j in range(n):
                    if grid[i][j]=='@':
                        x, y = i, j
                    elif grid[i][j].islower():
                        keys +=1
            return x, y, keys
        
        i0, j0, total_keys = get_start_and_keys()
        q=deque()
        start_point = (i0, j0, '')
        q.append(start_point)
        visited=set()
        visited.add(start_point)
        steps = -1
        while q:
            size=len(q)
            steps +=1
            for x in range(size):
                pop=q.popleft()
                i=pop[0]
                j=pop[1]
                keys=pop[2]
                if len(keys)==total_keys:
                    return steps
                for nex in move(i,j,keys):
                    if nex not in visited:
                        q.append(nex)
                        visited.add(nex)
        return -1
       
                
                
                
                
                
                
        
        
        


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m=len(grid)
        n=len(grid[0])
        
        # handles neighbor, returns neighbor next state
        def neighbor(i,j, keys):
            keys_list = list(keys)
            if grid[i][j] in ['.', '@']:
                return (i,j,keys)
            elif grid[i][j].islower():
                if grid[i][j] in keys_list: # already picked key, treat as empty cell
                    return (i,j,keys)
                else: # pick up new key
                    keys_list.append(grid[i][j])
                    new_keys=''.join(keys_list)
                    return (i,j,new_keys)
            elif grid[i][j].isupper():
                if grid[i][j].lower() in keys_list: # treat lock as empty cell if have the key
                    return (i,j,keys)
            return None
        
        def move(i,j,keys):
            nexts=[]
            if i>0:
                nei=neighbor(i-1,j,keys)
                if nei:
                    nexts.append(nei)
            if i<m-1:
                nei=neighbor(i+1,j,keys)
                if nei:
                    nexts.append(nei)
            if j>0:
                nei=neighbor(i,j-1,keys)
                if nei:
                    nexts.append(nei)
            if j<n-1:
                nei= neighbor(i,j+1,keys)
                if nei:
                    nexts.append(nei)
            return nexts
                  
        def get_start_and_keys():
            x, y, keys = -1, -1, 0
            for i in range(m):
                for j in range(n):
                    if grid[i][j]=='@':
                        x, y = i, j
                    elif grid[i][j].islower():
                        keys +=1
            return x, y, keys
        
        i0, j0, total_keys = get_start_and_keys()
        q=deque()
        start_point = (i0, j0, '')
        q.append(start_point)
        visited=set()
        visited.add(start_point)
        steps = -1
        while q:
            size=len(q)
            steps +=1
            for x in range(size):
                pop=q.popleft()
                i=pop[0]
                j=pop[1]
                keys=pop[2]
                if len(keys)==total_keys:
                    return steps
                for nex in move(i,j,keys):
                    if nex not in visited:
                        q.append(nex)
                        visited.add(nex)
        return -1 

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m=len(grid)
        n=len(grid[0])
        
        # handles neighbor, returns neighbor next state
        def neighbor(i,j, keys):
            keys_list = list(keys)
            if grid[i][j] in ['.', '@']:
                return (i,j,keys)
            elif grid[i][j].islower():
                if grid[i][j] in keys_list: # already picked key, treat as empty cell
                    return (i,j,keys)
                else: # pick up new key
                    keys_list.append(grid[i][j])
                    new_keys=''.join(keys_list)
                    return (i,j,new_keys)
            elif grid[i][j].isupper():
                if grid[i][j].lower() in keys_list: # treat lock as empty cell if have the key
                    return (i,j,keys)
            return None
        
        def move(i,j,keys):
            nexts=[]
            if i>0:
                nei=neighbor(i-1,j,keys)
                if nei:
                    nexts.append(nei)
            if i<m-1:
                nei=neighbor(i+1,j,keys)
                if nei:
                    nexts.append(nei)
            if j>0:
                nei=neighbor(i,j-1,keys)
                if nei:
                    nexts.append(nei)
            if j<n-1:
                nei= neighbor(i,j+1,keys)
                if nei:
                    nexts.append(nei)
            return nexts
                  
        def get_start_and_keys():
            x, y, keys = -1, -1, 0
            for i in range(m):
                for j in range(n):
                    if grid[i][j]=='@':
                        x, y = i, j
                    elif grid[i][j].islower():
                        keys +=1
            return x, y, keys
        
        i0, j0, total_keys = get_start_and_keys()
        q=deque()
        start_point = (i0, j0, '')
        q.append(start_point)
        visited=set()
        visited.add(start_point)
        steps = -1
        while q:
            size=len(q)
            steps +=1
            for x in range(size):
                pop=q.popleft()
                i=pop[0]
                j=pop[1]
                keys=pop[2]
                if len(keys)==total_keys:
                    return steps
                for nex in move(i,j,keys):
                    if nex not in visited:
                        q.append(nex)
                        visited.add(nex)
        return -1
       
                
                
                
                
                
                
        
        
        


import heapq
from collections import deque, defaultdict
class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m,n = len(grid),len(grid[0])
        key_lock_loc = {ch:(i,j) for i,row in enumerate(grid) for j,ch in enumerate(row) if ch not in {'.','#'}}

        def bfs_from(src):
            i,j = key_lock_loc[src]
            seen = [[False] *n for _ in range(m)]
            seen[i][j] = True
            # only locations which are not wall will be put into the queue
            dque = deque([(i,j,0)]) 
            dist = {}
            while dque:
                i,j,d = dque.popleft()
                ch = grid[i][j]
                if ch != src and ch != '.': # reaches lock or key
                    dist[ch] = d
                    continue
                # '#' or '.'
                for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                    if not (0<=x<m and 0<=y<n) or grid[x][y] == '#' or seen[x][y]:
                        continue
                    seen[x][y] = True
                    dque.append((x,y,d+1))
            return dist
        
        dists = {key_lock:bfs_from(key_lock) for key_lock in key_lock_loc}
        target_state = 2 ** sum(key_lock.islower() for key_lock in key_lock_loc)-1
        
        hq = [(0,'@',0)]
        final_dist = defaultdict(lambda: float('inf'))
        final_dist['@',0] = 0
        while hq:
            d,loc,state = heapq.heappop(hq)
            if final_dist[loc,state] < d:
                continue
            if state == target_state:
                return d
            for destination, d2 in list(dists[loc].items()):
                state2 = state
                if destination.islower(): # key
                    state2 |= (1 <<(ord(destination) - ord('a')))
                elif destination.isupper(): # loc
                    if not(state &(1 <<(ord(destination) - ord('A')))):
                        continue
                if d + d2 < final_dist[destination, state2]:
                    final_dist[destination, state2]= d + d2
                    heapq.heappush(hq,(d+d2,destination,state2))
        return -1
        
                    


class Solution:
    def __init__(self):
        self.DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        start_x, start_y = -1, -1
        target_keys = 0
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    start_x, start_y = i, j
                elif grid[i][j].islower():
                # elif grid[i][j] in 'abcdef':
                    target_keys |= 1 << (ord(grid[i][j]) - ord('a'))
                    # final_keys <<= 1
                    # final_keys |= 1
        
        pq = [(0, 0, start_x, start_y)]
        visited = set((0, start_x, start_y))

        while pq:
            curr_steps, curr_keys, x, y = heapq.heappop(pq)

            if curr_keys == target_keys:
                return curr_steps

            for delta_x, delta_y in self.DIR:
                next_x, next_y = x + delta_x, y + delta_y

                if not self.inbound(grid, next_x, next_y) or grid[next_x][next_y] == '#':
                    continue

                if grid[next_x][next_y] in 'ABCDEF':
                    if (curr_keys >> (ord(grid[next_x][next_y]) - ord('A'))) & 1:
                        next_keys = curr_keys
                    else:
                        continue
                elif grid[next_x][next_y] in 'abcdef':
                    next_keys = curr_keys | (1 << (ord(grid[next_x][next_y]) - ord('a')))
                else: # the next location is @ or .
                    next_keys = curr_keys

                if (next_keys, next_x, next_y) in visited:
                        continue

                heapq.heappush(pq, (curr_steps + 1, next_keys, next_x, next_y))
                visited.add((next_keys, next_x, next_y))
        return -1
                
    def inbound(self, grid, x, y):
        return 0 <= x < len(grid) and 0 <= y < len(grid[0])

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        
        keylock={'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'A':'a','B':'b','C':'c','D':'d','E':'e','F':'f'}
        
        m=len(grid)
        n=len(grid[0])
        
        #Find the start point and the bit representation of all keys
        keys_target=0
        for i in range(m):
            for j in range(n):
                if(grid[i][j]=='@'):
                    start=(i,j)
                elif(grid[i][j] in 'abcdef'):
                    keys_target=keys_target|(1<<keylock[grid[i][j]])
                    
       
        #Check if all keys have been acquired
        def keyAllAcquired(value):
            if((value & keys_target)==keys_target):
                return True
            else:
                return False
            
        #check if it can be passed and within the boundary
        def isMovable(i,j):
            if(0<=i<=m-1 and 0<=j<=n-1 and grid[i][j]!='#'):
                return True
            else:
                return False
    
        #State is defined as ((i,j),keyloc acquired)
        visited_states={(start[0],start[1],0)}
        q=collections.deque()
        q.append((start[0],start[1],0))
        
        
        #Use DFS to find the minimum paths to cover all available keys
        step=0
        while q:
            #
            q_len=len(q)
            #Pop q_len number of elements from left of q
            for _ in range(q_len):
                i,j,keys=q.popleft()
                #Return whenever all the keys in the grid are acquired
                if(keyAllAcquired(keys)):
                    return step
                
                #Move along 4 directions
                directs=[-1,0,1,0,-1]
                for d in range(4):
                    newi=i+directs[d]
                    newj=j+directs[d+1]
                    
                    #Before updating the state, check if the newi and newj is within the bound and don't hit
                    #the wall
                    if(isMovable(newi,newj)):
                        #Check the following cases and make the move
                        #Do nothing for other cases
                        #keys
                        if(grid[newi][newj] in 'abcdef'):
                            new_state=(newi,newj,keys|1<<keylock[grid[newi][newj]])
                            #check existence only for key
                            if(new_state not in visited_states):
                                visited_states.add(new_state)
                                q.append(new_state)
                        #locks 
                        elif(grid[newi][newj] in 'ABCDEF'):
                            lower_int=keylock[keylock[grid[newi][newj]]]
                            new_state=(newi,newj,keys|1<<(lower_int+6))
                            #Check key and exisitence for lock
                            if(keys & (1<<lower_int) and new_state not in visited_states):
                                visited_states.add(new_state)
                                q.append(new_state)
                                
                        #'.' or '@'     
                        elif(grid[newi][newj] in '.@' and (newi,newj,keys) not in visited_states):
                            visited_states.add((newi,newj,keys))
                            q.append((newi,newj,keys))
            step+=1

        return -1
            
                           
                           
                           
                            
                            
                            
                    
                
            
            
        
        
        
        


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m=len(grid)
        n=len(grid[0])
        
        # for any path, cannot pick the same key twice
        def neighbor(i,j, keys):
            res=[]
            keys_list = list(keys)
            if grid[i][j] in ['.', '@']:
                res.append((i,j,keys))
            elif grid[i][j].islower():
                if grid[i][j] in keys_list: # already picked key, treat as empty cell
                    res.append((i,j,keys))
                else: # pick up new key
                    keys_list.append(grid[i][j])
                    new_keys=''.join(keys_list)
                    res.append((i,j,new_keys))
            elif grid[i][j].isupper():
                if grid[i][j].lower() in keys_list: # treat cell as empty if have the key
                    res.append((i,j,keys))
            return res
        
        def move(i,j,keys):
            nexts=[]
            if i>0:
                x = neighbor(i-1,j,keys)
                if x:
                    nexts += x
            if i<m-1:
                nei=neighbor(i+1,j,keys)
                if nei:
                    nexts += nei
            if j>0:
                nei=neighbor(i,j-1,keys)
                if nei:
                    nexts += nei
            if j<n-1:
                nei= neighbor(i,j+1,keys)
                if nei:
                    nexts += nei
            #print('move nexts', nexts)
            return nexts
                  
        def get_start_and_keys():
            x, y, keys = -1, -1, 0
            for i in range(m):
                for j in range(n):
                    if grid[i][j]=='@':
                        x, y = i, j
                    if grid[i][j].islower():
                        keys +=1
            return x, y, keys
        
        
        i0, j0, total_keys = get_start_and_keys()
        #print(i0,j0,total_keys)
        q=deque()
        start_point = (i0, j0, '')
        q.append(start_point)
        visited=set()
        visited.add(start_point)
        steps = -1
        while q:
            size=len(q)
            #print('q',q)
            steps +=1
            for x in range(size):
                pop=q.popleft()
                #print(pop, end=' ')
                i=pop[0]
                j=pop[1]
                keys=pop[2]
                if len(keys)==total_keys:
                    return steps
                for nex in move(i,j,keys):
                    #print('nex', nex)
                    #print('visited', visited)
                    if nex not in visited:
                        q.append(nex)
                        visited.add(nex)
        return -1
       
                
                
                
                
                
                
        
        
        


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        
        keylock={'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'A':'a','B':'b','C':'c','D':'d','E':'e','F':'f'}
        
        m=len(grid)
        n=len(grid[0])
        
        #Find the start point and the bit representation of all keys
        keys_target=0
        for i in range(m):
            for j in range(n):
                if(grid[i][j]=='@'):
                    start=(i,j)
                elif(grid[i][j] in 'abcdef'):
                    keys_target=keys_target|(1<<keylock[grid[i][j]])
                    
       
        #Check if all keys have been acquired
        def keyAllAcquired(value):
            if((value & keys_target)==keys_target):
                return True
            else:
                return False
            
        #check if it can be passed and within the boundary
        def isMovable(i,j):
            if(0<=i<=m-1 and 0<=j<=n-1 and grid[i][j]!='#'):
                return True
            else:
                return False
    
        #State is defined as ((i,j),keyloc acquired)
        visited_states={(start,0)}
        q=collections.deque()
        q.append((start,0))
        
        
        #Use DFS to find the minimum paths to cover all available keys
        step=0
        while q:
            #
            q_len=len(q)
            #Pop q_len number of elements from left of q
            for _ in range(q_len):
                (i,j),keys=q.popleft()
                #Return whenever all the keys in the grid are acquired
                if(keyAllAcquired(keys)):
                    return step
                
                #Move along 4 directions
                directs=[-1,0,1,0,-1]
                for d in range(4):
                    newi=i+directs[d]
                    newj=j+directs[d+1]
                    
                    #Before updating the state, check if the newi and newj is within the bound and don't hit
                    #the wall
                    if(isMovable(newi,newj)):
                        #Check the following cases and make the move
                        #Do nothing for other cases
                        #keys
                        if(grid[newi][newj] in 'abcdef'):
                            new_state=((newi,newj),keys|1<<keylock[grid[newi][newj]])
                            #check existence only for key
                            if(new_state not in visited_states):
                                visited_states.add(new_state)
                                q.append(new_state)
                        #locks 
                        elif(grid[newi][newj] in 'ABCDEF'):
                            lower_int=keylock[keylock[grid[newi][newj]]]
                            new_state=((newi,newj),keys|1<<(lower_int+6))
                            #Check key and exisitence for lock
                            if(keys & (1<<lower_int) and new_state not in visited_states):
                                visited_states.add(new_state)
                                q.append(new_state)
                                
                        #'.' or '@'     
                        elif(grid[newi][newj] in '.@' and ((newi,newj),keys) not in visited_states):
                            visited_states.add(((newi,newj),keys))
                            q.append(((newi,newj),keys))
            step+=1

        return -1
            
                           
                           
                           
                            
                            
                            
                    
                
            
            
        
        
        
        


class Solution:
    # Naive, BFS, starting from the start point without any key.
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        row, col = len(grid), len(grid[0])
        x, y = None, None
        num_keys = 0
        for r in range(row):
            for c in range(col):
                if grid[r][c] == '@':
                    x, y = r, c
                elif grid[r][c] in 'abcdef':
                    num_keys += 1
        queue = collections.deque([(x, y, 0, 0, '.@abcdef')])  # r, c, steps, num_key, accessible
        dires = [1, 0, -1, 0, 1]
        visited = set()
        while queue:
            r, c, steps, cnt_keys, accessible = queue.popleft()
            if grid[r][c] in 'abcdef' and grid[r][c].upper() not in accessible:
                accessible += grid[r][c].upper()  # corresponding lock is accessible
                cnt_keys += 1
            if cnt_keys == num_keys:  # collected all keys
                return steps
            for d in range(len(dires) - 1):
                new_r, new_c = r + dires[d], c + dires[d + 1]
                if 0 <= new_r < row and 0 <= new_c < col and grid[r][c] in accessible:
                    if (new_r, new_c, accessible) not in visited:
                        visited.add((new_r, new_c, accessible))
                        queue.append((new_r, new_c, steps + 1, cnt_keys, accessible))
        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m=len(grid)
        n=len(grid[0])
        
        def neighbor(i,j, keys):
            res=[]
            keys_list = list(keys)
            if grid[i][j] in ['.', '@']:
                res.append((i,j,keys))
            elif grid[i][j].islower():
                if grid[i][j] in keys_list: # already picked key, treat as empty cell
                    res.append((i,j,keys))
                else: # pick up new key
                    keys_list.append(grid[i][j])
                    new_keys=''.join(keys_list)
                    res.append((i,j,new_keys))
            elif grid[i][j].isupper():
                if grid[i][j].lower() in keys_list: # treat lock as empty cell if have the key
                    res.append((i,j,keys))
            return res
        
        def move(i,j,keys):
            nexts=[]
            if i>0:
                nei = neighbor(i-1,j,keys)
                if nei:
                    nexts += nei
            if i<m-1:
                nei=neighbor(i+1,j,keys)
                if nei:
                    nexts += nei
            if j>0:
                nei=neighbor(i,j-1,keys)
                if nei:
                    nexts += nei
            if j<n-1:
                nei= neighbor(i,j+1,keys)
                if nei:
                    nexts += nei
            return nexts
                  
        def get_start_and_keys():
            x, y, keys = -1, -1, 0
            for i in range(m):
                for j in range(n):
                    if grid[i][j]=='@':
                        x, y = i, j
                    elif grid[i][j].islower():
                        keys +=1
            return x, y, keys
        
        i0, j0, total_keys = get_start_and_keys()
        q=deque()
        start_point = (i0, j0, '')
        q.append(start_point)
        visited=set()
        visited.add(start_point)
        steps = -1
        while q:
            size=len(q)
            steps +=1
            for x in range(size):
                pop=q.popleft()
                i=pop[0]
                j=pop[1]
                keys=pop[2]
                if len(keys)==total_keys:
                    return steps
                for nex in move(i,j,keys):
                    if nex not in visited:
                        q.append(nex)
                        visited.add(nex)
        return -1
       
                
                
                
                
                
                
        
        
        


from collections import defaultdict, deque
import heapq

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        oa = ord('a')
        oA = ord('A')
        m,n = len(grid),len(grid[0])
        key_lock_loc = {ch:(i,j) for i,row in enumerate(grid) for j,ch in enumerate(row) if ch not in '#.'}
        key_cnt = sum(ch.islower() for ch in key_lock_loc)
        
        def dfs_from(src):
            i,j = key_lock_loc[src]
            seen = defaultdict(lambda: False)
            seen[i,j] = True
            dque = deque([(i,j,0)])
            dist = {}
            while dque:
                i,j,d = dque.popleft()
                ch = grid[i][j]
                if ch != src and ch != '.':
                    dist[ch] = d
                    continue
                for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                    if not (0<=x<m and 0<=y<n) or grid[x][y] == '#' or seen[x,y]:
                        continue
                    dque.append((x,y,d+1))
                    seen[x,y] = True
            return dist
        
        dists = {ch:dfs_from(ch) for ch in key_lock_loc}
        target_state = 2**key_cnt - 1
        final_dist = defaultdict(lambda: float('inf'))
        hq = [(0,'@',0)] # (dist, ch, state)
        final_dist['@',0] = 0
        while hq:
            d, ch, state = heapq.heappop(hq)
            if d > final_dist[ch,state]:
                continue
            if state == target_state:
                return d
            
            for ch1,d1 in dists[ch].items():
                state1 = state
                if ch1.islower():
                    state1 |= 1<< (ord(ch1)-oa)
                elif ch1.isupper() and not (state1 & 1<< (ord(ch1)-oA)):
                        continue
                if d + d1 < final_dist[ch1,state1]:
                    final_dist[ch1,state1] = d + d1
                    heapq.heappush(hq,(d+d1, ch1, state1))
        return -1

import heapq
from collections import deque, defaultdict
class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m,n = len(grid),len(grid[0])
        key_lock_loc = {ch:(i,j) for i,row in enumerate(grid) for j,ch in enumerate(row) if ch not in {'.','#'}}
        key_cnt = sum(key_lock.islower() for key_lock in key_lock_loc)

        def bfs_from(src):
            i,j = key_lock_loc[src]
            seen = [[False] *n for _ in range(m)]
            seen[i][j] = True
            # only locations which are not wall will be put into the queue
            dque = deque([(i,j,0)]) 
            dist = {}
            while dque:
                i,j,d = dque.popleft()
                ch = grid[i][j]
                if ch != src and ch != '.': # reaches lock or key
                    dist[ch] = d
                    continue
                # '#' or '.'
                for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                    if not (0<=x<m and 0<=y<n) or grid[x][y] == '#' or seen[x][y]:
                        continue
                    seen[x][y] = True
                    dque.append((x,y,d+1))
            return dist
        
        dists = {key_lock:bfs_from(key_lock) for key_lock in key_lock_loc}
        all_keys_bitmap = 2 ** key_cnt -1
        
        hq = [(0,'@',0)]
        final_dist = defaultdict(lambda: float('inf'))
        final_dist['@',0] = 0
        while hq:
            d,ch,keys_bitmap = heapq.heappop(hq)
            if final_dist[ch,keys_bitmap] < d:
                continue
            if keys_bitmap == all_keys_bitmap:
                return d
            for next_key_lock, d2 in list(dists[ch].items()):
                keys_bitmap2 = keys_bitmap
                if next_key_lock.islower(): # key
                    keys_bitmap2 |= (1 <<(ord(next_key_lock) - ord('a')))
                elif next_key_lock.isupper(): # ch
                    if not(keys_bitmap &(1 <<(ord(next_key_lock) - ord('A')))):
                        continue
                if d + d2 < final_dist[next_key_lock, keys_bitmap2]:
                    final_dist[next_key_lock, keys_bitmap2]= d + d2
                    heapq.heappush(hq,(d+d2,next_key_lock,keys_bitmap2))
        return -1
        
                    


class Solution:
    def shortestPathAllKeys(self, grid):
        m,n,k,keys,d=len(grid),len(grid[0]),0,'',set()
        grid.append('#'*n)
        for i in range(m): grid[i]+='#'
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='@': si,sj=i,j
                elif grid[i][j] in 'abcdef': keys+=grid[i][j]
        a,keyss=[(si,sj,keys)],''.join([c.upper() for c in keys])
        while a:
            b=[]
            for i,j,keys in a:
                keys = keys.replace(grid[i][j], '')# keys=''.join([c for c in keys if c!=grid[i][j]])
                if not keys: return k
                for ii,jj in (i,j+1),(i+1,j),(i,j-1),(i-1,j):
                    if grid[ii][jj]!='#' and (not(grid[ii][jj] in keyss and grid[ii][jj].lower() in keys)) and ((ii,jj,keys) not in d):
                        d.add((ii,jj,keys))
                        b.append((ii,jj,keys))
            a,k=b,k+1
        return -1

class Solution:
    def shortestPathAllKeys(self, grid):
        m,n,k,keys,d=len(grid),len(grid[0]),0,'',set()
        grid.append('#'*n)
        for i in range(m): grid[i]+='#'
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='@': si,sj=i,j
                elif grid[i][j] in 'abcdef': keys+=grid[i][j]
        a,keyss=[(si,sj,keys)],''.join([c.upper() for c in keys])
        while a:
            b=[]
            for i,j,keys in a:
                #if grid[i][j] in keys: keys = keys.replace(grid[i][j], '')# keys=''.join([c for c in keys if c!=grid[i][j]])
                keys = keys.replace(grid[i][j], '')# keys=''.join([c for c in keys if c!=grid[i][j]])
                if not keys: return k
                for ii,jj in (i,j+1),(i+1,j),(i,j-1),(i-1,j):
                    if grid[ii][jj]!='#' and (not(grid[ii][jj] in keyss and grid[ii][jj].lower() in keys)) and ((ii,jj,keys) not in d):
                        d.add((ii,jj,keys))
                        b.append((ii,jj,keys))
            a,k=b,k+1
        return -1

class Solution:
    def shortestPathAllKeys(self, grid):
        m,n,k,keys,d=len(grid),len(grid[0]),0,'',set()
        grid.append('#'*n)
        for i in range(m): grid[i]+='#'
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='@': si,sj=i,j
                elif grid[i][j] in 'abcdef': keys+=grid[i][j]
        a,keyss=[(si,sj,keys)],''.join([c.upper() for c in keys])
        while a:
            b=[]
            for i,j,keys in a:
                if grid[i][j] in keys: keys = keys.replace(grid[i][j], '')# keys=''.join([c for c in keys if c!=grid[i][j]])
                if not keys: return k
                for ii,jj in (i,j+1),(i+1,j),(i,j-1),(i-1,j):
                    if grid[ii][jj]!='#' and (not(grid[ii][jj] in keyss and grid[ii][jj].lower() in keys)) and ((ii,jj,keys) not in d):
                        d.add((ii,jj,keys))
                        b.append((ii,jj,keys))
            a,k=b,k+1
        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m,n,k,keys,d=len(grid),len(grid[0]),0,'',set()
        grid.append('#'*n)
        for i in range(m): grid[i]+='#'
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='@': si,sj=i,j
                elif grid[i][j] in 'abcdef': keys+=grid[i][j]
        a,keyss=[(si,sj,keys)],''.join([c.upper() for c in keys])
        while a:
            b=[]
            for i,j,keys in a:
                if grid[i][j] in keys: keys=''.join([c for c in keys if c!=grid[i][j]])
                if not keys: return k
                for ii,jj in (i,j+1),(i+1,j),(i,j-1),(i-1,j):
                    if grid[ii][jj]!='#' and (not(grid[ii][jj] in keyss and grid[ii][jj].lower() in keys)) and ((ii,jj,keys) not in d):
                        d.add((ii,jj,keys))
                        b.append((ii,jj,keys))
            a,k=b,k+1
        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        def bfs(r, c):
            start = grid[r][c]
            dist[start] = {}
            queue = collections.deque([(r, c, 0)])
            visited = {(r, c): True}
            while queue:
                i, j, d = queue.pop()
                if grid[i][j] not in ['.', '#', start]:
                    dist[start][grid[i][j]] = d
                    continue
                for ic, jc in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:
                    if 0 <= ic < m and 0 <= jc < n and (ic, jc) not in visited and grid[ic][jc] != '#':
                        visited[(ic, jc)] = True
                        queue.appendleft((ic, jc, d + 1))
        
        m, n = len(grid), len(grid[0])
        dist = {}
        for r in range(m):
            for c in range(n):
                if grid[r][c] not in ['.', '#']:
                    bfs(r, c)
        
        prioq = [(0, '@', 0)] # distance, place, state
        target_state = 0
        visited = {}
        for key in dist:
            if 'a' <= key <= 'f':
                target_state += 1 << (ord(key) - ord('a'))
                
        while prioq:
            d, p, state = heapq.heappop(prioq)
            if (p, state) in visited: continue
            if state == target_state: return d
            visited[(p, state)] = True
            for dest, moves in list(dist[p].items()):
                if 'A' <= dest <= 'F' and 1 << (ord(dest) - ord('A')) & state == 0:
                    continue
                new_state = state
                if 'a' <= dest <= 'f':
                    new_state |= 1 << (ord(dest) - ord('a'))
                if (dest, new_state) not in visited:
                    heapq.heappush(prioq, (d + moves, dest, new_state))
        return -1


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m = len(grid)
        n = len(grid[0])
        q = collections.deque()
        keys = 0
        visited = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    q.append((i, j, 0))
                    visited.add((i, j, 0))
                elif grid[i][j] >= 'a' and grid[i][j] <= 'f':
                    keys += 1
        goal = (1 << keys) - 1
        
        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        step = 0
        while q:
            size = len(q)
            for _ in range(size):
                i, j, state = q.popleft()
                for di, dj in dirs:
                    x = i + di
                    y = j + dj
                    
                    if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == '#' or (x, y, state) in visited:
                        continue
                    
                    nstate = state
                    if grid[x][y] >= 'A' and grid[x][y] <= 'F':
                        temp = ord(grid[x][y]) - ord('A')
                        if state & (1 << temp) == 0:
                            continue
                    elif grid[x][y] >= 'a' and grid[x][y] <= 'f':
                        temp = ord(grid[x][y]) - ord('a')
                        nstate |= 1 << temp
                        if nstate == goal:
                            return step + 1
                        
                    visited.add((x, y, nstate))
                    q.append((x, y, nstate))
                
            step += 1
        
        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        #30*30*2^6 =900*64--10^5 < 10^6
        
        init_x, init_y = -1, -1
        m = len(grid)
        n = len(grid[0])
        keycnt = 0

        for i in range(m):
            for j in range(n):
                c = grid[i][j]
                if c == '@':
                    init_x, init_y = i, j
                if c >= 'a' and c <= 'f':
                    keycnt +=1
        
        init_state = (0, init_x, init_y)
        q = collections.deque()
        visited = set()
        visited.add(init_state)
        q.append(init_state)
        steps = -1 
        finalkey = 0
        
    
        for i in range(keycnt):
            finalkey |= (1 << i) 
        
        while q:
            lens = len(q)
            steps += 1
            
            for _ in range(len(q)):
                keys, x, y = q.popleft()
                for nx, ny in ((x+1, y), (x-1, y),(x, y+1), (x, y-1)):
                    
                    if 0 > nx or nx >= m or 0 > ny or ny >=n:
                        continue
                        
                    new_s = keys
                    c = grid[nx][ny]
                    if c == '#':
                        continue

                    if c >= 'A' and c <= 'F' and ((keys >> (ord(c) - ord('A'))) & 1 == 0):
                        continue

                    if c >= 'a' and c <= 'f':
                        new_s |=  (1 << (ord(c) - ord('a')))
                    
                    if (new_s, nx, ny) in visited:
                        continue
                    if new_s == finalkey:
                        return steps + 1
                
                    visited.add((new_s, nx, ny))
                    q.append((new_s, nx, ny))
                
        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        if not grid:
            return -1
        keys=[0]*6
        m,n=len(grid),len(grid[0])
        si,sj=0,0
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='@':
                    si,sj=i,j
                if grid[i][j].islower():
                    keys[ord(grid[i][j])-ord('a')]=1
        mykeys=tuple(keys)
        
        q=[(si,sj,tuple([0]*6))]
        visited={(si,sj,tuple([0]*6))}
        c=0
        while q:
            nextq=[]
            for i,j,keys in q:
                for x,y in ((i+1,j),(i-1,j),(i,j-1),(i,j+1)):
                    if 0<=x<m and 0<=y<n and grid[x][y]!='#':
                        if grid[x][y] in '.@':
                            if (x,y,keys) not in visited:
                                nextq.append((x,y,keys))
                                visited.add((x,y,keys))
                        elif grid[x][y].islower():
                            okeys=list(keys)
                            okeys[ord(grid[x][y])-ord('a')]=1
                            nkeys=tuple(okeys)
                            if nkeys==mykeys:
                                return c+1
                            else:
                                if (x,y,nkeys) not in visited:
                                    nextq.append((x,y,nkeys))
                                    visited.add((x,y,nkeys))
                        elif grid[x][y].isupper():
                            if keys[ord(grid[x][y].lower())-ord('a')]==1 and (x,y,keys) not in visited:
                                nextq.append((x,y,keys))
                                visited.add((x,y,keys))
            c+=1
            q=nextq
        return -1
                            
            
            


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        keys = 'abcdef'
        locks = 'ABCDEF'
        n, m = len(grid), len(grid[0])
        x, y = -1, -1
        target = 0
        for i in range(n):
            for j in range(m):
                ch = grid[i][j]
                if ch == '@':
                    x, y = i, j
                elif ch in keys:
                    idx = keys.find(ch)
                    target |= (1<<idx)
                
        visited = set()
        visited.add((x,y,0))
        q = deque()
        q.append((x,y,0,0))
        while q:
            x, y, state, move = q.popleft()
            if state == target:
                return move
            for dx, dy in [[-1,0],[1,0],[0,-1],[0,1]]:
                dx += x
                dy += y
                tmp = state
                if dx < 0 or dy < 0 or dx >= n or dy >= m:
                    continue
                ch = grid[dx][dy]
                if ch == '#':
                    continue
                
                if ch in locks:
                    idx = locks.find(ch)
                    # print(dx,dy,ch,idx)
                    if state & (1<<idx) == 0:
                        continue
                if ch in keys:
                    idx = keys.find(ch)
                    tmp |= (1<<idx)
                if (dx,dy,tmp) not in visited:
                    visited.add((dx,dy,tmp))
                    q.append((dx,dy,tmp,move+1))
        return -1



class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        
        q = collections.deque()
        seen = set()
        tot_keys = 0
        for i, row in enumerate(grid):
            for j, val in enumerate(row):
                if val == '@':
                    q.append((i, j, 0))
                    seen.add((i, j, 0))
                elif val in 'ABCDEF':
                    tot_keys += 1
        steps = 0
        while q:
            N = len(q)
            for _ in range(N):
                x, y, keys = q.popleft()
                if keys == (1 << tot_keys) - 1:
                    return steps
                for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                    if (0 <= nx < m and 0 <= ny < n):
                        if grid[nx][ny] == '#': continue
                        if grid[nx][ny] in 'ABCDEF' and not (keys >> ord(grid[nx][ny]) - ord('A')) & 1:
                            continue
                        nxt = keys
                        if grid[nx][ny] in 'abcdef':
                            nxt |= (1 << ord(grid[nx][ny]) - ord('a'))
                        if (nx, ny, nxt) not in seen:
                            seen.add((nx, ny, nxt))
                            q.append((nx, ny, nxt))
            steps += 1
        return -1    
                        
                            
        


from collections import deque
class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        ## BFS search
        dirs = [[0,1],[0,-1],[1,0],[-1,0]]
        m = len(grid)
        n = len(grid[0])
        visited = set()
        q = deque()
        cnt = 0
        ## find the starting point and count how many keys are there
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    q.append((i, j, 0))
                    visited.add((i, j, 0))
                elif grid[i][j] in 'abcdef':
                    cnt += 1
                    
        keys = set('abcdef')
        locks = set('ABCDEF')
        ## use bit mask to represent how many keys we have
        ## the target is to collect all keys, i.e, 2**(cnt)-1
        target = 2**(cnt)-1
        steps = 0
        while len(q)>0:
            q_sz = len(q)
            for _ in range(q_sz):
                x, y, cur_keys = q.popleft()
                if cur_keys == target:
                    return steps
                for d in dirs:
                    next_x, next_y = x+d[0], y+d[1]
                    pos_flag = False ## mark if the next position is legal
                    if 0<=next_x<m and 0<=next_y<n and grid[next_x][next_y] != '#':
                        new_keys = cur_keys
                        ## if the next position is a lock:
                        ## we must have its corresponding key to make a legal
                        ## otherwise, cannot reach next position
                        if grid[next_x][next_y] in locks:
                            lock = ord(grid[next_x][next_y]) - ord('A')
                            if (1<<lock) & cur_keys != 0:
                                pos_flag = True
                        ## if the next position is a key
                        elif grid[next_x][next_y] in keys:
                            key = ord(grid[next_x][next_y]) - ord('a')
                            new_keys = cur_keys | (1<<key) ## collect the key
                            pos_flag = True
                        else: ## the next position is '.'
                            pos_flag = True
                        ## only when the next position is legal
                        ## and we have not reach there with current keys,
                        ## we will reach there and search 
                        if pos_flag and (next_x, next_y, new_keys) not in visited:
                            visited.add((next_x, next_y, new_keys))
                            q.append((next_x, next_y, new_keys))
            steps += 1
        return -1

from collections import deque
class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        dirs = [[0,1],[0,-1],[1,0],[-1,0]]
        m = len(grid)
        n = len(grid[0])
        visited = set()
        q = deque()
        cnt = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    q.append((i, j, 0))
                    visited.add((i, j, 0))
                elif grid[i][j] in 'abcdef':
                    cnt += 1
                    
        keys = set('abcdef')
        locks = set('ABCDEF')
        target = 2**(cnt)-1
        steps = 0
        while len(q)>0:
        # for _ in range(3):
            q_sz = len(q)
            for _ in range(q_sz):
                x, y, cur_keys = q.popleft()
                # print(\"steps\", steps, \":\", x, y, cur_keys)
                if cur_keys == target:
                    return steps
                for d in dirs:
                    next_x, next_y = x+d[0], y+d[1]
                    pos_flag = False
                    if 0<=next_x<m and 0<=next_y<n and grid[next_x][next_y] != '#':
                        new_keys = cur_keys
                        if grid[next_x][next_y] in locks:
                            lock = ord(grid[next_x][next_y]) - ord('A')
                            if (1<<lock) & cur_keys != 0:
                                pos_flag = True
                        elif grid[next_x][next_y] in keys:
                            key = ord(grid[next_x][next_y]) - ord('a')
                            new_keys = cur_keys | (1<<key)
                            pos_flag = True
                        else:
                            pos_flag = True
                            
                        if pos_flag and (next_x, next_y, new_keys) not in visited:
                            # print(\"steps\", steps, \":\", next_x, next_y, cur_keys)
                            visited.add((next_x, next_y, new_keys))
                            q.append((next_x, next_y, new_keys))
            steps += 1
        return -1
# [\"@.a.#\",\"###.#\",\"b.A.B\"]
# [\"@..aA\",\"..B#.\",\"....b\"]


from collections import defaultdict, deque
import heapq

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        ord_a = ord('a')
        ord_A = ord('A')
        m,n = len(grid), len(grid[0])
        key_lock_loc = {ch:(i,j) for i,row in enumerate(grid) for j,ch in enumerate(row) if ch not in '.#'}
        key_cnt = sum(ch.islower() for ch in key_lock_loc)
        
        def dfs_from(src):
            i,j  = key_lock_loc[src]
            dque = deque([(i,j,0)])
            seen = defaultdict(lambda: False)
            seen[i,j] = True
            dist = {}
            while dque:
                i,j,d = dque.popleft()
                ch = grid[i][j]
                if ch != src and ch!= '.':
                    dist[ch] = d
                    continue
                for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                    if not (0<=x<m and 0<=y<n) or grid[x][y]=='#' or seen[x,y]:
                        continue
                    dque.append((x,y,d+1))
                    seen[x,y] = True
            return dist
    
        dists = {ch:dfs_from(ch) for ch in key_lock_loc}
        final_dist = defaultdict(lambda: float('inf'))
        hq = [(0,'@',0)] # distance, ch, state
        final_state = 2**key_cnt - 1
        
        while hq:
            d, ch, state = heapq.heappop(hq)
            if d > final_dist[ch,state]:
                continue
            if state == final_state:
                return d
            for ch1,d1 in list(dists[ch].items()):
                state1 = state
                if ch1.islower():
                    state1 |= 1<< (ord(ch1)-ord_a)
                elif ch1.isupper():
                    if not (state1 &1<< (ord(ch1)-ord_A)):
                        continue
                if d + d1 < final_dist[ch1,state1]:
                    final_dist[ch1,state1] = d + d1
                    heapq.heappush(hq,(d+d1, ch1, state1))
        return -1
        
            


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        if not grid:
            return -1
        m, n = len(grid), len(grid[0])
        numKeys = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    start = (i, j, 0)
                elif ord('a') <= ord(grid[i][j]) <= ord('f'):
                    numKeys += 1
        bfs = [start]
        seen = set()
        d = [1, 0, -1, 0, 1]
        step = 0
        while bfs:
            cur, bfs = bfs, []
            for x, y, keys in cur:
                # print(len(keys))
                if keys == (1 << numKeys) - 1:
                    return step
                # print(x, y, keys, locks)
                for i in range(4):
                    xx, yy = x + d[i], y + d[i+1]
                    if 0 <= xx < m and 0 <= yy < n and (xx, yy, keys) not in seen:
                        seen.add((xx, yy, keys))
                        if ord('a') <= ord(grid[xx][yy]) <= ord('f'):
                            bfs.append((xx, yy, keys | (1 << (ord(grid[xx][yy]) - ord('a')))))
                        elif ord('A') <= ord(grid[xx][yy]) <= ord('F'):
                            if (1 << (ord(grid[xx][yy].lower()) - ord('a'))) & keys == 0:
                                continue
                            else:
                                bfs.append((xx, yy, keys))
                            # bfs.append((xx, yy, keys, locks | (1 << (ord(grid[xx][yy]) - ord('A')))))
                        elif grid[xx][yy] == '.' or grid[xx][yy] == '@':
                            bfs.append((xx, yy, keys))
            step += 1
            
        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        mx_key = max(grid[i][j] for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j].isalpha() and grid[i][j].islower())
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=='@':
                    si,sj = i,j
                    break
        needed_keys = (1<<(ord(mx_key)-ord('a')+1))-1
        def key_id(c):
            if c.isupper():
                return ord(c)-ord('A'), True
            return ord(c)-ord('a'), False # id, upper
        seen = {(si,sj,0)}
        q = deque([(0,si,sj,0)]) #cost,i,j,keys
        while q:
            cost,i,j,keys=q.popleft()
            if keys==needed_keys:
                return cost
            for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                if not 0<=ni<len(grid) or not 0<=nj<len(grid[0]) or grid[ni][nj]=='#':
                    continue
                # get new keys bitset
                new_keys = keys
                if grid[ni][nj].isalpha():
                    idx,capped = key_id(grid[ni][nj])
                    if capped:
                        if not keys&(1<<idx):
                            continue # cant enter a door we dont have a key to
                    else:
                        new_keys|=1<<idx
                if (ni,nj,new_keys) in seen:
                    continue
                seen.add((ni,nj,new_keys))
                q.append((cost+1,ni,nj,new_keys))
        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        if not grid or not grid[0]:
            return -1
        m, n = len(grid), len(grid[0])
        sx = sy = target = -1
        for i in range(m):
            for j in range(n):
                c = grid[i][j]
                if c == '@':
                    sx, sy = i, j
                if c >= 'a' and c <= 'f':
                    target = max(target, ord(c)-ord('a')+1)
        target = (1 << target) - 1
        q = deque([(sx, sy, 0)])
        visited = set()
        visited.add(q[0])
        step = 0
        while q:
            for _ in range(len(q)):
                x, y, key = q.popleft()
                if key == target:
                    return step
                for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                    if x+i >= 0 and x+i < m and y+j >= 0 and y+j < n:
                        c = grid[x+i][y+j]
                        new_key = key
                        if c == '#':
                            continue
                        if c >= 'A' and c <= 'F' and (key >> (ord(c)-ord('A')) & 1 == 0):
                            continue
                        if c >='a' and c <= 'f':
                            new_key |= 1 << (ord(c)-ord('a'))
                        if (x+i, y+j, new_key) not in visited:
                            visited.add((x+i, y+j, new_key))
                            q.append((x+i, y+j, new_key))
            step += 1
        return -1
                


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        import heapq
        import collections
        R, C = len(grid), len(grid[0])

        # The points of interest
        location = {v: (r, c)
                    for r, row in enumerate(grid)
                    for c, v in enumerate(row)
                    if v not in '.#'}

        def neighbors(r, c):
            for cr, cc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
                if 0 <= cr < R and 0 <= cc < C:
                    yield cr, cc

        # The distance from source to each point of interest
        def bfs_from(source):
            r, c = location[source]
            seen = [[False] * C for _ in range(R)]
            seen[r][c] = True
            queue = collections.deque([(r, c, 0)])
            dist = {}
            while queue:
                r, c, d = queue.popleft()
                if source != grid[r][c] != '.':
                    dist[grid[r][c]] = d
                    continue  # Stop walking from here if we reach a point of interest
                for cr, cc in neighbors(r, c):
                    if grid[cr][cc] != '#' and not seen[cr][cc]:
                        seen[cr][cc] = True
                        queue.append((cr, cc, d + 1))
            return dist

        dists = {place: bfs_from(place) for place in location}
        target_state = 2 ** sum(p.islower() for p in location) - 1

        # Dijkstra
        pq = [(0, '@', 0)]
        final_dist = collections.defaultdict(lambda: float('inf'))
        final_dist['@', 0] = 0
        while pq:
            d, place, state = heapq.heappop(pq)
            if final_dist[place, state] < d: continue
            if state == target_state: return d
            for destination, d2 in dists[place].items():
                state2 = state
                if destination.islower():  # key
                    state2 |= (1 << (ord(destination) - ord('a')))
                elif destination.isupper():  # lock
                    if not (state & (1 << (ord(destination) - ord('A')))):  # no key
                        continue

                if d + d2 < final_dist[destination, state2]:
                    final_dist[destination, state2] = d + d2
                    heapq.heappush(pq, (d + d2, destination, state2))

        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        # bfs: x,y, ownkeys -> n*m* 2^6
        
        def have_keys(status, key_id):
            return status & (2**key_id)
        
        sx, sy = -1, -1
        key_number = 0
        key_idx = 'abcdef'
        lock_idx = 'ABCDEF'
        n, m = len(grid), len(grid[0])
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '@':
                    sx, sy = i, j
                elif grid[i][j] in key_idx:
                    key_number = max(key_number, key_idx.find(grid[i][j]))
        #print(sx, sy)
        #print(key_number)
        # bfs: (x, y, ownkeys)
        final_ownkey = 2 ** (key_number+1) - 1
        head, queue = 0, [(sx, sy, 0)]
        moves = [(0,1), (0,-1), (1,0), (-1,0)]
        
        visited = {(sx, sy, 0): 0}
        
        while head < len(queue):
            x, y, status = queue[head]
            step = visited[queue[head]]
            #print(x, y, status)
            #print(step)
            for dx, dy in moves:
                tx, ty, new_status = x + dx, y + dy, status
                if n > tx >= 0 and m > ty >=0:
                    # wall?
                    if grid[tx][ty] == '#':
                        continue
                        
                    # locked
                    if grid[tx][ty] in lock_idx and not have_keys(new_status, lock_idx.find(grid[tx][ty])):
                        continue
                        
                    # first time pick up key
                    if grid[tx][ty] in key_idx and not have_keys(new_status, key_idx.find(grid[tx][ty])):
                        new_status += 2 ** key_idx.find(grid[tx][ty])
                    
                    if new_status == final_ownkey:
                        return step + 1
                    
                    if (tx, ty, new_status) not in visited:
                        queue.append((tx, ty, new_status))
                        visited[(tx, ty, new_status)] = step + 1
            #print(queue)
            head += 1
            
        return -1
            
        
            
        
        
        


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        if not grid or not grid[0]:
            return -1
        m, n = len(grid), len(grid[0])
        sx = sy = target = -1
        for i in range(m):
            for j in range(n):
                c = grid[i][j]
                if c == '@':
                    sx, sy = i, j
                if c >= 'a' and c <= 'f':
                    target = max(target, ord(c)-ord('a')+1)
        print((target, ))
        target = (1 << target) - 1
        print(target)
        q = deque([(sx, sy, 0)])
        visited = set()
        visited.add(q[0])
        step = 0
        while q:
            print(q)
            for _ in range(len(q)):
                x, y, key = q.popleft()
                if key == target:
                    return step
                for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                    if x+i >= 0 and x+i < m and y+j >= 0 and y+j < n:
                        c = grid[x+i][y+j]
                        new_key = key
                        if c == '#':
                            continue
                        if c >= 'A' and c <= 'F' and (key >> (ord(c)-ord('A')) & 1 == 0):
                            continue
                        if c >='a' and c <= 'f':
                            new_key |= 1 << (ord(c)-ord('a'))
                        if (x+i, y+j, new_key) not in visited:
                            visited.add((x+i, y+j, new_key))
                            q.append((x+i, y+j, new_key))
            step += 1
        return -1
                


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        def contains(k, v):
            return (k // v) % 2 == 1
            
        adjs = [[-1, 0], [0, 1], [0, -1], [1, 0]]
        keys = ['a', 'b', 'c', 'd', 'e', 'f']
        locks = [c.upper() for c in keys]
        key_to_val = {k: 2**i for i, k in enumerate(keys)}
        lock_to_val = {k: 2**i for i, k in enumerate(locks)}
        N, M = len(grid), len(grid[0])
        visited = [[[-1]*64 for _ in range(M)] for _ in range(N)]
        
        queue = deque()
        target = 0
        for i in range(N):
            for j in range(M):
                if grid[i][j] == '@': 
                    queue.append([i, j, 0])
                    visited[i][j][0] = 0
                if grid[i][j] in keys: target += key_to_val[grid[i][j]]
        if target == 0: return 0
        
        while len(queue) > 0:
            i, j, k = queue.popleft()
            for di, dj in adjs:
                ii, jj = i + di, j + dj
                if ii >= 0 and jj >= 0 and ii < N and jj < M:
                    if grid[ii][jj] in ('.', '@') and visited[ii][jj][k] < 0:
                        visited[ii][jj][k] = visited[i][j][k] + 1
                        queue.append((ii, jj, k))
                    elif grid[ii][jj] in keys:
                        if not contains(k, key_to_val[grid[ii][jj]]):
                            kk = k + key_to_val[grid[ii][jj]]
                            if kk == target: return visited[i][j][k] + 1
                        else:
                            kk = k
                        if visited[ii][jj][kk] < 0:
                            visited[ii][jj][kk] = visited[i][j][k] + 1
                            queue.append((ii, jj, kk))
                    elif grid[ii][jj] in locks and contains(k, lock_to_val[grid[ii][jj]]) and visited[ii][jj][k] < 0:
                        visited[ii][jj][k] = visited[i][j][k] + 1
                        queue.append((ii, jj, k))
        return -1
                            


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        res,dire,all_keys = 0, [[0,1],[1,0],[0,-1],[-1,0]],0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '@': loc = (i,j)
                if grid[i][j] in 'abcdef': all_keys += 1
        cur, seen= set([(loc,())]), set([(loc,())])
        def checker(loc,keys,di):
            x,y = loc[0] + di[0], loc[1] + di[1]
            if 0<=x < len(grid) and 0<= y < len(grid[0]):
                t = grid[x][y]
                if t in '@.' or (t in keys) or (t in 'ABCDEF' and str.lower(t) in keys): return ((x,y),keys), False
                if t in 'abcdef': 
                        newkeys = tuple(sorted(set(list(keys) + [t])))
                        if len(newkeys) == all_keys: return True, True
                        return ((x,y),newkeys), False
            return False, False
        while cur:
            res,tmp = res + 1, []
            for node in cur:
                loc, keys = node
                for di in dire:
                    new_node,state = checker(loc,keys,di)
                    if state: return res
                    if new_node not in seen and new_node: tmp += [new_node]
            cur = set(tmp)
            seen |= cur
        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        R, C = len(grid), len(grid[0])

        # The points of interest
        location = {v: (r, c)
                    for r, row in enumerate(grid)
                    for c, v in enumerate(row)
                    if v not in '.#'}

        def neighbors(r, c):
            for cr, cc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
                if 0 <= cr < R and 0 <= cc < C:
                    yield cr, cc

        # The distance from source to each point of interest
        def bfs_from(source):
            r, c = location[source]
            seen = [[False] * C for _ in range(R)]
            seen[r][c] = True
            queue = collections.deque([(r, c, 0)])
            dist = {}
            while queue:
                r, c, d = queue.popleft()
                if source != grid[r][c] != '.':
                    dist[grid[r][c]] = d
                    continue # Stop walking from here if we reach a point of interest
                for cr, cc in neighbors(r, c):
                    if grid[cr][cc] != '#' and not seen[cr][cc]:
                        seen[cr][cc] = True
                        queue.append((cr, cc, d+1))
            return dist        

        dists = {place: bfs_from(place) for place in location}
        target_state = 2 ** sum(p.islower() for p in location) - 1

        #Dijkstra
        pq = [(0, '@', 0)]
        final_dist = collections.defaultdict(lambda: float('inf'))
        final_dist['@', 0] = 0
        while pq:
            d, place, state = heapq.heappop(pq)
            if final_dist[place, state] < d: continue
            if state == target_state: return d
            for destination, d2 in dists[place].items():
                state2 = state
                if destination.islower(): #key
                    state2 |= (1 << (ord(destination) - ord('a')))
                elif destination.isupper(): #lock
                    if not(state & (1 << (ord(destination) - ord('A')))): #no key
                        continue

                if d + d2 < final_dist[destination, state2]:
                    final_dist[destination, state2] = d + d2
                    heapq.heappush(pq, (d+d2, destination, state2))

        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        from collections import deque
        start = [0,0]
        numofKeys = 0
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    start = [i,j]
                if grid[i][j].isalpha():
                    numofKeys += 1
        numofKeys //= 2
        keys = 0
        visited = set()
        stack = deque([[start[0],start[1], 0, 0]])
        while stack:
            #print(stack)
            i, j, keys, count = stack.popleft()
            for a, b in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
                if 0<=a<m and 0<=b<n:
                    if grid[a][b].isalpha() and ord('a')<=ord(grid[a][b])<=ord('f'):
                        newkeys = keys|(1<<(ord(grid[a][b])-ord('a')))
                    elif grid[a][b].isalpha() and keys&(1<<(ord(grid[a][b])-ord('A'))):
                        newkeys = keys
                    elif grid[a][b].isalpha() or grid[a][b] == '#':
                        continue
                    else:
                        newkeys = keys
                    
                    if newkeys == 2**numofKeys-1:
                        return count+1
                    elif (a,b,newkeys) in visited:
                        continue
                    else:
                        visited.add((a,b,newkeys))
                        stack.append((a,b,newkeys, count+1))
        return -1
                            
                        


class Solution:
    def shortestPathAllKeys(self, grid) -> int:
        row,col = len(grid),len(grid[0])
        key_num,key = 0,{}
        for i in range(row):
            for j in range(col):
                if grid[i][j]=='@': start_i,start_j=i,j
                if grid[i][j] in 'abcdef' and grid[i][j] not in key:
                    key[grid[i][j]]=key_num
                    key_num+=1
        q = [(start_i,start_j,0,0)]
        visited = set()
        while q:
            l = len(q)
            for _ in range(l):
                i,j,state,step = q.pop(0)
                if state==(1<<key_num)-1: return step
                if (i,j,state) in visited: continue
                visited.add((i,j,state))
                for m,n in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                    if 0<=m<row and 0<=n<col and grid[m][n]!='#':
                        if grid[m][n] in 'abcdef':
                            q.append((m,n,state|(1<<key[grid[m][n]]),step+1))
                        elif grid[m][n] == '.' or grid[m][n] =='@':
                            q.append((m,n,state,step+1))
                        elif grid[m][n] in 'ABCDEF':
                            if (state>>key[grid[m][n].lower()])&1==0: continue
                            q.append((m,n,state,step+1))
        return -1
                     
                        
            
                    
                

        


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        R, C = len(grid), len(grid[0])
        ii, jj =0 ,0 
        target = 0
        for i in range(R):
            for j in range(C):
                if grid[i][j]=='@':
                    ii, jj = i, j
                if grid[i][j].islower():
                    target+=1
        def bfs(i, j):
            from collections import deque
            Q = deque([(i,j, 0 ,set())])
            seen = {(i,j,tuple(sorted(set())))}
            while Q:
                i,j, d, s = Q.popleft()
                for di, dj in [(0,1),(1,0),(0,-1),(-1,0)]:
                    r, c = i+di, j+dj
                    if 0<=r<R and 0<=c<C:
                        if grid[r][c].islower():
                            #s1 = s
                            s1 =  s.copy()
                            s1.add(grid[r][c])
                            if len(s1)==target:return d+1
                            tuple_s = tuple(sorted(set(s1)))
                            if (r,c,tuple_s) not in seen:
                                seen.add((r,c,tuple_s))
                                Q.append((r,c, d+1,s1))
                        elif grid[r][c].isupper():
                            if grid[r][c].lower() in s:
                                tuple_s = tuple(sorted(set(s)))
                                if (r,c,tuple_s) not in seen:
                                    seen.add((r,c,tuple_s))
                                    Q.append((r,c,  d+1, s))
                        elif grid[r][c]!='#':
                            tuple_s = tuple(sorted(set(s)))
                            if (r,c,tuple_s) not in seen:
                                seen.add((r,c,tuple_s))
                                Q.append((r,c, d+1, s))
            return -1
        return bfs(ii,jj)

from collections import defaultdict, deque
import heapq, itertools

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        # Brute Force + Permutations
        # Time  complexity: O(R x C x A x A!), where R, C are the dimensions of the grid,
        # and A is the maximum number of keys.
        # Space compleixty: O(R x C + A!)
        # R, C = map(len, (grid, grid[0]))
        # location = {v: (r, c)
        #             for r, row in enumerate(grid)
        #             for c, v in enumerate(row)
        #             if v not in '.#'}

        # def neighbors(r, c):
        #     for cr, cc in (r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1):
        #         if 0 <= cr < R and 0 <= cc < C:
        #             yield cr, cc

        # def bfs(source, target, keys=()):
        #     sr, sc = location[source]
        #     tr, tc = location[target]
        #     seen = [[False] * C for _ in range(R)]
        #     seen[sr][sc] = True
        #     queue = deque([(sr, sc, 0)])
        #     while queue:
        #         r, c, d = queue.popleft()
        #         if r == tr and c == tc: return d
        #         for cr, cc in neighbors(r, c):
        #             if not seen[cr][cc] and grid[cr][cc] != '#':
        #                 if grid[cr][cc].isupper() and grid[cr][cc].lower() not in keys:
        #                     continue
        #                 queue.append((cr, cc, d + 1))
        #                 seen[cr][cc] = True
        #     return float(\"inf\")

        # ans = float(\"inf\")
        # keys = \"\".join(chr(ord('a') + i) for i in range(len(location) // 2))
        # for cand in itertools.permutations(keys):
        #     bns = 0
        #     for i, target in enumerate(cand):
        #         source = cand[i - 1] if i > 0 else '@'
        #         d = bfs(source, target, cand[:i])
        #         bns += d
        #         if bns >= ans: break
        #     else:
        #         ans = bns

        # return ans if ans < float(\"inf\") else -1



        # Points of Interest + Dijkstra
        # Time  complexity: O(RC(2A + 1) + ElogN), where R, C are the dimensions of the grid, 
        # and A is the maximum number of keys, N = (2A + 1) x 2^A is the number of nodes when we
        # perform Dijkstra's, and E = N x (2A + 1) is the maximum number of edges.
        # Space complexity: ON(N)
        R, C = len(grid), len(grid[0])

        # The points of interest
        location = {v: (r, c)
                    for r, row in enumerate(grid)
                    for c, v in enumerate(row)
                    if v not in '.#'}

        def neighbors(r, c):
            for cr, cc in (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1):
                if 0 <= cr < R and 0 <= cc < C:
                    yield cr, cc

        # The distance from source to each point of interest
        def bfs_from(source):
            r, c = location[source]
            seen = [[False] * C for _ in range(R)]
            seen[r][c] = True
            queue = deque([(r, c, 0)])
            dist = {}
            while queue:
                r, c, d = queue.popleft()
                if source != grid[r][c] != '.':
                    dist[grid[r][c]] = d
                    continue # Stop walking from here if we reach a point of interest
                for cr, cc in neighbors(r, c):
                    if grid[cr][cc] != '#' and not seen[cr][cc]:
                        seen[cr][cc] = True
                        queue.append((cr, cc, d+1))
            return dist        

        dists = {place: bfs_from(place) for place in location}
        target_state = 2 ** sum(p.islower() for p in location) - 1

        #Dijkstra
        pq = [(0, '@', 0)]
        final_dist = defaultdict(lambda: float('inf'))
        final_dist['@', 0] = 0
        while pq:
            d, place, state = heapq.heappop(pq)
            if final_dist[place, state] < d: continue
            if state == target_state: return d
            for destination, d2 in list(dists[place].items()):
                state2 = state
                if destination.islower(): #key
                    state2 |= 1 << ord(destination) - ord('a')
                elif destination.isupper(): #lock
                    if not(state & (1 << ord(destination) - ord('A'))): #no key
                        continue

                if d + d2 < final_dist[destination, state2]:
                    final_dist[destination, state2] = d + d2
                    heapq.heappush(pq, (d+d2, destination, state2))

        return -1


class Solution:
    def __init__(self):
        self.DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def shortestPathAllKeys(self, grid: List[str]) -> int:
        init_x = init_y = -1
        target_keys = 0

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '@':
                    init_x, init_y = i, j
                elif grid[i][j].islower():
                    target_keys |= 1 << (ord(grid[i][j]) - ord('a'))

        pq = [(0, 0, init_x, init_y)]
        visited = set((0, init_x, init_y))

        while pq:
            curr_steps, curr_keys, x, y = heapq.heappop(pq)

            if curr_keys == target_keys:
                return curr_steps

            for delta_x, delta_y in self.DIR:
                next_x, next_y = x + delta_x, y + delta_y

                if not self.inbound(grid, next_x, next_y) or grid[next_x][next_y] == '#':
                    continue

                if grid[next_x][next_y].isupper():
                    if (curr_keys >> (ord(grid[next_x][next_y]) - ord('A'))) & 1:
                        next_keys = curr_keys
                    else:
                        continue
                elif grid[next_x][next_y].islower():
                    next_keys = curr_keys | (1 << (ord(grid[next_x][next_y]) - ord('a')))
                else: # the next location is @ or .
                    next_keys = curr_keys

                if (next_keys, next_x, next_y) in visited:
                    continue

                heapq.heappush(pq, (curr_steps + 1, next_keys, next_x, next_y))
                visited.add((next_keys, next_x, next_y))

        return -1

    def inbound(self, grid, x, y):
        return 0 <= x < len(grid) and 0 <= y < len(grid[0])

from collections import deque
dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        k = 0
        m, n = len(grid), len(grid[0])
        sr, sc = None, None
        for r in range(m):
            for c in range(n):
                if grid[r][c] == '@':
                    sr, sc = r, c
                elif grid[r][c] in 'abcdefABCDEF':
                    k = max(k, ord(grid[r][c].lower()) - ord('a') + 1)
        dp = [[[float('inf') for z in range(1 << k)] for y in range(n)] for x in range(m)]
        dp[sr][sc][0] = 0
        dq = deque([(sr, sc, 0, 0)])
        while dq:
            size = len(dq)
            for i in range(size):
                r, c, ks, s = dq.popleft() # key state, step
                for d in dirs:
                    nr, nc = r + d[0], c + d[1]
                    if not (0 <= nr < m) or not (0 <= nc < n):
                        continue
                    elif grid[nr][nc] == '#':
                        continue
                    elif grid[nr][nc] in '.@': # empty cell or starting point
                        if s + 1 < dp[nr][nc][ks]:
                            dp[nr][nc][ks] = s + 1
                            dq.append((nr, nc, ks, s + 1))
                    elif grid[nr][nc] in 'ABCDEF':
                        lock = ord(grid[nr][nc]) - ord('A')
                        if ks & (1 << lock):
                            if s + 1 < dp[nr][nc][ks]:
                                dp[nr][nc][ks] = s + 1
                                dq.append((nr, nc, ks, s + 1))
                    elif grid[nr][nc] in 'abcdef':
                        key = ord(grid[nr][nc]) - ord('a')
                        nks = ks | (1 << key)
                        if s + 1 < dp[nr][nc][nks]:
                            dp[nr][nc][nks] = s + 1
                            dq.append((nr, nc, nks, s + 1))
        ret = float('inf')
        for r in range(m):
            for c in range(n):
                ret = min(ret, dp[r][c][-1])
        return ret if ret != float('inf') else -1
                


from collections import defaultdict, deque
import heapq, itertools

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        # Brute Force + Permutations
        # Time  complexity: O(R x C x A x A!), where R, C are the dimensions of the grid,
        # and A is the maximum number of keys.
        # Space compleixty: O(R x C + A!)
        # R, C = map(len, (grid, grid[0]))
        # location = {v: (r, c)
        #             for r, row in enumerate(grid)
        #             for c, v in enumerate(row)
        #             if v not in '.#'}

        # def neighbors(r, c):
        #     for cr, cc in (r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1):
        #         if 0 <= cr < R and 0 <= cc < C:
        #             yield cr, cc

        # def bfs(source, target, keys=()):
        #     sr, sc = location[source]
        #     tr, tc = location[target]
        #     seen = [[False] * C for _ in range(R)]
        #     seen[sr][sc] = True
        #     queue = deque([(sr, sc, 0)])
        #     while queue:
        #         r, c, d = queue.popleft()
        #         if r == tr and c == tc: return d
        #         for cr, cc in neighbors(r, c):
        #             if not seen[cr][cc] and grid[cr][cc] != '#':
        #                 if grid[cr][cc].isupper() and grid[cr][cc].lower() not in keys:
        #                     continue
        #                 queue.append((cr, cc, d + 1))
        #                 seen[cr][cc] = True
        #     return float(\"inf\")

        # ans = float(\"inf\")
        # keys = \"\".join(chr(ord('a') + i) for i in range(len(location) // 2))
        # for cand in itertools.permutations(keys):
        #     bns = 0
        #     for i, target in enumerate(cand):
        #         source = cand[i - 1] if i > 0 else '@'
        #         d = bfs(source, target, cand[:i])
        #         bns += d
        #         if bns >= ans: break
        #     else:
        #         ans = bns

        # return ans if ans < float(\"inf\") else -1



        # Points of Interest + Dijkstra
        # Time  complexity: O(RC(2A + 1) + ElogN), where R, C are the dimensions of the grid, 
        # and A is the maximum number of keys, N = (2A + 1) x 2^A is the number of nodes when we
        # perform Dijkstra's, and E = N x (2A + 1) is the maximum number of edges.
        # Space complexity: ON(N)
        R, C = len(grid), len(grid[0])

        # The points of interest
        location = {v: (r, c)
                    for r, row in enumerate(grid)
                    for c, v in enumerate(row)
                    if v not in '.#'}

        def neighbors(r, c):
            for cr, cc in (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1):
                if 0 <= cr < R and 0 <= cc < C:
                    yield cr, cc

        # The distance from source to each point of interest
        def bfs_from(source):
            r, c = location[source]
            seen = [[False] * C for _ in range(R)]
            seen[r][c] = True
            queue = deque([(r, c, 0)])
            dist = {}
            while queue:
                r, c, d = queue.popleft()
                if source != grid[r][c] != '.':
                    dist[grid[r][c]] = d
                    continue # Stop walking from here if we reach a point of interest
                for cr, cc in neighbors(r, c):
                    if grid[cr][cc] != '#' and not seen[cr][cc]:
                        seen[cr][cc] = True
                        queue.append((cr, cc, d + 1))
            return dist        

        dists = {place: bfs_from(place) for place in location}
        target_state = 2 ** sum(p.islower() for p in location) - 1

        #Dijkstra
        pq = [(0, '@', 0)]
        final_dist = defaultdict(lambda: float('inf'))
        final_dist['@', 0] = 0
        while pq:
            d, place, state = heapq.heappop(pq)
            if final_dist[place, state] < d: continue
            if state == target_state: return d
            for destination, d2 in list(dists[place].items()):
                state2 = state
                if destination.islower(): #key
                    state2 |= 1 << ord(destination) - ord('a')
                elif destination.isupper(): #lock
                    if not(state & (1 << ord(destination) - ord('A'))): #no key
                        continue

                if d + d2 < final_dist[destination, state2]:
                    final_dist[destination, state2] = d + d2
                    heapq.heappush(pq, (d + d2, destination, state2))

        return -1


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        
        k = 0
        stx, sty = 0, 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] in 'abcdef': k += 1
                if grid[i][j] == '@': stx = i; sty = j
        
        def keys(mask):
            ans = 0
            for m in [1, 2, 4, 8, 16, 32]:
                if mask & m: ans += 1
            return ans
        
        def neighbors(i, j):
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                if i+dx < 0 or i+dx >= m or j+dy < 0 or j + dy >= n: continue
                if grid[i+dx][j+dy] == '#': continue
                    
                yield i+dx, j+dy
                
        q = collections.deque()
        seen = set()
        
        q.append((stx, sty, 0, 0))
        while q:
            i, j, mask, moves = q.popleft()
            if grid[i][j] in 'ABCDEF':
                id = 'ABCDEF'.index(grid[i][j])
                if not mask & (1 << id): continue
                    
            if (i, j, mask) in seen: continue
            seen.add((i, j, mask))
            
            if keys(mask) == k: return moves - 1

            if grid[i][j] in 'abcdef':
                mask |= (1 << (ord(grid[i][j]) - ord('a')))
                
            for ii, jj in neighbors(i, j):
                q.append((ii, jj, mask, moves+1))
            
        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        from heapq import heappush, heappop
        R, C = len(grid), len(grid[0])
        start = None
        K = 0
        for r in range(R):
            for c in range(C):
                if grid[r][c] == '@':
                    start = (r, c)
                elif grid[r][c].isupper():
                    K = max(K, ord(grid[r][c]) - ord('A') + 1)
        
        assert start is not None
        assert K > 0
        
        h = [(0, *start, 0)]
        seen = set()
        while h:
            m, r, c, keys = heappop(h)
            if (r, c, keys) in seen:
                continue
            seen.add((r, c, keys))
            if keys == (1 << K) - 1:
                return m
            for rp, cp in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
                if 0 <= rp < R and 0 <= cp < C:
                    char = grid[rp][cp]
                    if char == '#' or char.isupper() and keys & (1 << (ord(char) - ord('A'))) == 0:
                        continue
                    new_keys = keys
                    if char.islower():
                        new_keys |= (1 << (ord(char) - ord('a')))
                    heappush(h, (m+1, rp, cp, new_keys))
        return -1
                        
                        
                        


from collections import deque
class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        keyMap = {ch : 1 << offset for offset, ch in enumerate('abcdef')}
        
        def hasKey(state, key):
            return state & keyMap[key]
        def setKey(state, key):
            return state | keyMap[key]        
        # BFS?
        keys = set()
        start = None
        target = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if 'a' <= grid[i][j] <= 'f':
                    target = setKey(target, grid[i][j])
                elif grid[i][j] == '@':
                    start = (i, j)
        def neighbors(i, j):
            moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
            for di, dj in moves:
                if 0 <= i + di < len(grid) and 0 <= j + dj < len(grid[0]) and grid[i][j] != '#':
                    yield (i + di, j + dj)
        

        visited = set()      
        q = deque([[start, 0, 0]])
        while q:
            coord, oldKeys, steps = q.popleft()
            for n in neighbors(coord[0], coord[1]):
                newKeys = oldKeys
                c = grid[n[0]][n[1]]
                if 'A' <= c <= 'F' and not hasKey(newKeys, c.lower()):
                    continue            

                if 'a' <= c <= 'f':
                    newKeys = setKey(newKeys, c)

                if newKeys == target:
                    return steps + 1

                if (n, newKeys) not in visited:
                    visited.add((n, newKeys))
                    q.append([n, newKeys, steps + 1])
        return -1
        
        
        
        
        


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        sr, sc = 0, 0
        k, m, n = 0, len(grid), len(grid[0])
        key_id = collections.defaultdict(int)
        for i, x in enumerate('abcdef'):
            key_id[x] = i + 1
        for r in range(m):
            for c in range(n):
                if grid[r][c] == '@':
                    sr, sc = r, c
                k = max(k, key_id[grid[r][c]])
        q = [(sr, sc, '')]
        res = 0
        vis = set((sr, sc, ''))
        while q:
            tmp = []
            for r, c, keys in q:
                if len(keys) == k:
                    return res
                for rr, cc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
                    if 0<= rr < m and 0<= cc < n and grid[rr][cc] != '#':
                        x = grid[rr][cc]
                        if x in 'ABCDEF' and x.lower() not in keys:
                            continue
                        new_keys = keys[::]
                        if x in 'abcdef' and x not in new_keys:
                            new_keys += x
                        if (rr, cc, new_keys) not in vis:
                            vis.add((rr, cc, new_keys))
                            tmp.append((rr, cc, new_keys))
            res += 1
            q = tmp
        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        
        
        n, m = len(grid), len(grid[0])
        
        startx, starty = -1,-1
        nkeys = 0
        
        for i in range(n):
            
            for j in range(m):
                
                if grid[i][j] == '@':
                    
                    startx, starty = i,j
                    
                if grid[i][j] in 'abcdef':
                    
                    nkeys += 1
                    
        queue = deque([(startx,starty,0,'',0)])
        
        visited = set([(startx,starty,'')])
        
        while queue:
            
            node = queue.popleft()
            
            x,y,nkey,keys,moves = node
            
            if nkey == nkeys:
                return moves
            
            for ni in [(x+1,y), (x,y+1), (x-1,y), (x,y-1)]:
                
                xx,yy = ni
                
                if xx < 0 or yy < 0 or xx >=n or yy >=m or grid[xx][yy] == '#':
                    continue
              
                if grid[xx][yy] in 'ABCDEF':
                    if grid[xx][yy].lower() in keys and (xx,yy,keys) not in visited:
                        queue.append(((xx,yy,nkey,keys,moves+1)))
                        visited.add((xx,yy,keys))
                    
                elif grid[xx][yy] in 'abcdef' and grid[xx][yy] not in keys:      
                    visited.add((xx,yy,keys+grid[xx][yy]))
                    queue.append((xx,yy,nkey+1,keys+grid[xx][yy],moves+1))
                    
                elif (xx,yy,keys) not in visited:
                    visited.add((xx,yy,keys))
                    queue.append((xx,yy,nkey,keys,moves+1))
                    
        return -1

                    


import heapq
from collections import deque, defaultdict
class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m,n = len(grid),len(grid[0])
        key_lock_loc = {ch:(i,j) for i,row in enumerate(grid) for j,ch in enumerate(row) if ch not in {'.','#'}}
        key_cnt = sum(key_lock.islower() for key_lock in key_lock_loc)

        def bfs_from(src):
            i,j = key_lock_loc[src]
            seen = [[False] *n for _ in range(m)]
            seen[i][j] = True
            # only locations which are not wall will be put into the queue
            dque = deque([(i,j,0)]) 
            dist = {}
            while dque:
                i,j,d = dque.popleft()
                ch = grid[i][j]
                if ch != src and ch != '.': # reaches lock or key
                    dist[ch] = d
                    continue
                # '#' or '.'
                for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                    if not (0<=x<m and 0<=y<n) or grid[x][y] == '#' or seen[x][y]:
                        continue
                    seen[x][y] = True
                    dque.append((x,y,d+1))
            return dist
        
        dists = {key_lock:bfs_from(key_lock) for key_lock in key_lock_loc}
        target_state = 2 ** key_cnt -1
        
        hq = [(0,'@',0)]
        final_dist = defaultdict(lambda: float('inf'))
        final_dist['@',0] = 0
        while hq:
            d,loc,state = heapq.heappop(hq)
            if final_dist[loc,state] < d:
                continue
            if state == target_state:
                return d
            for destination, d2 in list(dists[loc].items()):
                state2 = state
                if destination.islower(): # key
                    state2 |= (1 <<(ord(destination) - ord('a')))
                elif destination.isupper(): # loc
                    if not(state &(1 <<(ord(destination) - ord('A')))):
                        continue
                if d + d2 < final_dist[destination, state2]:
                    final_dist[destination, state2]= d + d2
                    heapq.heappush(hq,(d+d2,destination,state2))
        return -1
        
                    


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        q, seen, keys = deque(), set(), set()        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    q.append((i,j,''))
                    seen.add((i,j,''))
                elif 'a' <= grid[i][j] <= 'f':
                    keys.add(grid[i][j])
        
        steps = 0
        while q:
            size = len(q)
            #print(list(q), grid[q[0][0]][q[0][1]])
            for _ in range(size):
                x,y,k = q.popleft()
                if len(k) == len(keys): return steps
                for i,j in [(0,1), (0,-1), (1,0), (-1,0)]:
                    nx, ny, nk = x + i, y + j, k
                    if nx < 0 or nx >= m or ny < 0 or ny >= n or grid[nx][ny] == '#':
                        continue
                    if 'A' <= grid[nx][ny] <= 'F' and grid[nx][ny].lower() not in nk:
                        continue
                    if 'a' <= grid[nx][ny] <= 'f' and grid[nx][ny] not in nk:
                        nk += grid[nx][ny]
                    if (nx,ny,nk) not in seen:
                        q.append((nx,ny,nk))
                        seen.add((nx,ny,nk))
            steps += 1
        return -1

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        # simple BFS. store a bag of keys you have and when encounter a lock,
        # check whether you have corresponding key in the bag
        target = 0
        queue, visited = [], set()
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if 'a' <= grid[i][j] <= 'f':
                    target += 1
                elif grid[i][j] == '@':
                    queue.append((i, j, '.@abcdef', 0))
                    visited.add((i, j, '.@abcedf'))
        
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        ans = 0
        collected = set()
        
        while len(queue) != 0:
            size = len(queue)
            for _ in range(size):
                x, y, bag, collected = queue.pop(0)
                if collected == target:
                    return ans
                for ix, iy in dirs:
                    xx = x+ix
                    yy = y+iy
                    if 0 <= xx < len(grid) and 0 <= yy < len(grid[0]) and grid[xx][yy] in bag:
                        if 'a' <= grid[xx][yy] <= 'f' and grid[xx][yy].upper() not in bag:
                            if (xx, yy, bag+grid[xx][yy].upper()) not in visited:
                                queue.append((xx, yy, bag+grid[xx][yy].upper(), collected+1))
                                visited.add((xx, yy, bag+grid[xx][yy].upper()))
                        else:
                            if (xx, yy, bag) not in visited:
                                queue.append((xx, yy, bag, collected))
                                visited.add((xx, yy, bag))
            ans += 1
        return -1

'''
[\"@.a.#\",\"###.#\",\"b.A.B\"]

[
\"@.a.#\",
\"###.#\",
\"b.A.B\"
]


[
\"@..aA\",
\"..B#.\",
\"....b\"
]


'''

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        n, m = len(grid), len(grid[0])
        
        queue = collections.deque()
        seen = set()
        nKeys = 0
        moves = 0
        
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '@':
                    queue.append([i, j, 0, 0, 'abcdef.@'])
                elif grid[i][j] in 'abcdef':
                    nKeys += 1
        
        while queue:
            i, j, moves, curKeys, keys = queue.popleft()
            
            if grid[i][j] in 'abcdef' and grid[i][j].upper() not in keys:
                keys += grid[i][j].upper()
                curKeys += 1
            
            if curKeys == nKeys:
                return moves
            
            for x, y in (-1, 0), (1, 0), (0, -1), (0, 1):
                ni, nj = i + x, j + y
                if 0 <= ni < n and 0 <= nj < m and grid[ni][nj] in keys and  (ni, nj, keys) not in seen:
                    seen.add((ni, nj, keys))
                    queue.append([ni, nj, moves + 1, curKeys, keys])
        
        return -1