You are given an m x n grid grid where:


	'.' is an empty cell.
	'#' is a wall.
	'@' is the starting point.
	Lowercase letters represent keys.
	Uppercase letters represent locks.


You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall.

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

For some 1 &lt;= k &lt;= 6, there is exactly one lowercase and one uppercase letter of the first k letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys. If it is impossible, return -1.

&nbsp;
Example 1:

Input: grid = ["@.a..","###.#","b.A.B"]
Output: 8
Explanation: Note that the goal is to obtain all the keys not to open all the locks.


Example 2:

Input: grid = ["@..aA","..B#.","....b"]
Output: 6


Example 3:

Input: grid = ["@Aa"]
Output: -1


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 30
	grid[i][j] is either an English letter, '.', '#', or '@'.
	The number of keys in the grid is in the range [1, 6].
	Each key in the grid is unique.
	Each key in the grid has a matching lock.


class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        
        m=len(grid)
        n=len(grid[0])
        visited=set()
        
        steps=0
        q=deque([])
        keyCt=0
        
        for i in range(m):
            for j in range(n):
                if grid[i][j]=="@":
                    q.append((i,j,''))
                elif grid[i][j].islower():
                    keyCt+=1
        
        while q:
            for _ in range(len(q)):
                curr_x,curr_y,keys = q.popleft()
                if (curr_x,curr_y,keys) in visited:
                    continue
                
                visited.add((curr_x,curr_y,keys))
                
                if len(keys)==keyCt:
                    return steps
                
                for x,y in ((0,1),(1,0),(-1,0),(0,-1)):
                    nx=curr_x+x
                    ny=curr_y+y
                    if nx<0 or ny<0 or nx>=m or ny>=n or grid[nx][ny]=='#' or (nx,ny,keys) in visited:
                        continue
                        
                    curr=grid[nx][ny]                    
                    if curr in 'abcdef' and curr not in keys:
                        q.append((nx,ny,keys+curr))                            
                    elif curr.isupper() and curr.lower() not in keys:
                        continue
                    else:
                        q.append((nx,ny,keys))
            steps+=1
        
        return -1
class Solution {
    
    private static final int[][] DIRS = new int[][]{ 
        {1,0}, {-1,0}, {0,1}, {0,-1}
    };
    
    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        int numKeys = 0, startRow = -1, startCol = -1;
        
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                char c = grid[i].charAt(j);
                
                if( isStart(c) ) {
                    startRow = i;
                    startCol = j;
                } 
                else if( isKey(c) )
                    numKeys++;
            }
        }
        if( startRow == -1 ) return -1;
        
        int keyMask = (1 << numKeys) - 1;
        State start = new State(startRow, startCol, 0);
        Queue<State> queue = new LinkedList();
        Set<State> visited = new HashSet();   
        int steps = 0;
        
        queue.offer(start);
        visited.add(start);
        
        while( !queue.isEmpty() ) {
            int size = queue.size();
            
            while( size-- > 0 ) {
                int i = queue.peek().i;
                int j = queue.peek().j;
                int keys = queue.peek().keys;
                queue.poll();
                
                if( keys == keyMask )
                    return steps;
                
                for(int[] dir : DIRS) {
                    int di = i + dir[0];
                    int dj = j + dir[1];
                    int newKeys = keys;

                    if( di < 0 || dj < 0 || di == m || dj == n )
                        continue;

                    char c = grid[di].charAt(dj);

                    if( isWall(c) ) continue;
                    
                    if( isLock(c) && !isKeyPresent(keys, c) )
                        continue;

                    if( isKey(c) ) 
                        newKeys |= (1 << (c - 'a'));
                    
                    State newState = new State(di, dj, newKeys);
                    
                    if( visited.add(newState) ) 
                        queue.offer(newState);
                }
            }
            steps++;
        }
        return -1;
    }
    
    private boolean isLock(char c) {
        return c >= 'A' && c <= 'Z';
    }
    private boolean isKey(char c) {
        return c >= 'a' && c <= 'z';
    }
    private boolean isWall(char c) {
        return c == '#';
    }
    private boolean isStart(char c) {
        return c == '@';
    }
    private boolean isKeyPresent(int keys, char lock) {
        return (keys & (1 << (lock-'A'))) != 0;
    }
}
class State {
    public int i, j, keys;
    
    public State(int i, int j, int keys) {
        this.i = i;
        this.j = j;
        this.keys = keys;
    }
    
    @Override
    public boolean equals(Object obj) {
        if( !(obj instanceof State) ) return false;
        State that = (State)obj;
        return i == that.i && j == that.j && keys == that.keys;
    }
    
    @Override
    public int hashCode() {
        int prime = 31;
        int hash = 1;
        hash = hash * prime + i;
        hash = hash * prime + j;
        hash = hash * prime + keys;
        return hash;
    }
}
class Solution {
    int dirx[4] = {-1,1,0,0};
    int diry[4] = {0,0,1,-1};
public:
    int shortestPathAllKeys(vector<string>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> matrix(n, vector<int>(m));
        vector<int> lock(7,0);
        int sx, sy;
        int lk = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(grid[i][j] == '@')
                {
                    sx = i, sy = j;
                    matrix[i][j] = 0;
                }
                else if(grid[i][j] == '.')
                {
                    matrix[i][j] = 0;
                    //cout << grid[i][j];
                }
                else if(grid[i][j] >= 'A' && grid[i][j] <= 'F')
                {
                    matrix[i][j] = -1*((grid[i][j]-'A') + 1);
                    lock[(grid[i][j]-'A') + 1] = (1 << (grid[i][j]-'A'));
                }
                else if(grid[i][j] == '#')
                    matrix[i][j] = -8;
                else
                {
                    matrix[i][j] = (1 << (grid[i][j]-'a'));
                    lk++;
                }
                //cout << matrix[i][j] << " ";
            }
            //cout << endl;
        }
        int fnl = (1 << lk) - 1;
        //cout << fnl;
        vector<vector<int>> visited(n*m, vector<int>(fnl,1));
        queue<pair<pair<int,int>,int>> q;
        int ans = 0;
        q.push({{sx,sy},0});
        visited[sx*m+sy][0] = 0;
        while(!q.empty())
        {
            ans++;
            int sz = q.size();
            while(sz--)
            {
                int x = q.front().first.first;
                int y = q.front().first.second;
                int bit = q.front().second;
                q.pop();
                for(int i = 0; i < 4; i++)
                {
                    int nxtx = x + dirx[i];
                    int nxty = y + diry[i];
                    if(nxtx >= n || nxtx < 0 || nxty >= m || nxty < 0) continue;
                    if(matrix[nxtx][nxty] == -8) continue;
                    if(visited[nxtx*m+nxty][bit] == 0) continue;
                    if(matrix[nxtx][nxty] < 0)
                    {
                        int lkidx = -1*matrix[nxtx][nxty];
                        if(bit&lock[lkidx])
                        {
                            q.push({{nxtx,nxty},bit});
                            visited[nxtx*m+nxty][bit] = 0;
                        }
                    }
                    else if(matrix[nxtx][nxty] == 0)
                    {
                        q.push({{nxtx,nxty},bit});
                        visited[nxtx*m+nxty][bit] = 0;
                        continue;
                    }
                    else
                    {
                        int fbit = bit | matrix[nxtx][nxty];
                        if(fbit == fnl) return ans;
                        q.push({{nxtx,nxty},fbit});
                        visited[nxtx*m+nxty][fbit] = 0;
                    }
                }
            }
        }
        return -1;
    }
};
var shortestPathAllKeys = function(grid) {
    const n = grid.length;
    const m = grid[0].length;

    function isKey(letter) {
        return (
            letter.charCodeAt(0) >= 'a'.charCodeAt(0) && letter.charCodeAt(0) <= 'z'.charCodeAt(0)
        );
    }

    function isLock(letter) {
        return (
            letter.charCodeAt(0) >= 'A'.charCodeAt(0) && letter.charCodeAt(0) <= 'Z'.charCodeAt(0)
        );
    }

    const dns = [
        [1, 0],
        [0, 1],
        [-1, 0],
        [0, -1],
    ];

    let start = { x: 0, y: 0, keys: new Set() };
    let keyMap = new Map();

    for (let y = 0; y < n; ++y) {
        for (let x = 0; x < m; ++x) {
            const cell = grid[y][x];
            if (cell === '@') {
                start.x = x;
                start.y = y;
            } else if (isKey(cell)) {
                keyMap.set(cell, [x, y]);
            }
        }
    }

    function attemptToGetKey(x, y, keys, kx, ky) {
        let q = [[x, y, keys, 0]];
        let v = new Set();
        while (q.length) {
            let nextQueue = [];
            for (let i = 0; i < q.length; ++i) {
                const [x, y, keys, steps] = q[i];
                if (x === kx && ky === y) {
                    keys.add(grid[ky][kx]);
                    return { keysAcquired: keys, movesUsed: steps };
                }
                const locationHash = x + y * m;
                if (v.has(locationHash)) continue;
                v.add(locationHash);
                const cell = grid[y][x];
                if (cell !== '.') {
                    if (isLock(cell) && !keys.has(cell.toLowerCase())) {
                        continue;
                    }
                    if (isKey(cell)) {
                        keys.add(cell);
                    }
                }
                for (const [mx, my] of dns) {
                    const nx = x + mx;
                    const ny = y + my;
                    const nextHash = ny * m + nx;
                    if (grid[ny]?.[nx] != null && grid[ny]?.[nx] !== '#') {
                        if (!v.has(nextHash)) {
                            q.push([nx, ny, new Set(Array.from(keys)), steps + 1]);
                        }
                    }
                }
            }
            q = nextQueue;
        }
        return { keysAcquired: null, movesUsed: 0 };
    }

    let q = new MinPriorityQueue();
    q.enqueue([start.x, start.y, start.keys], 0);
    while (q.size()) {
        const { element, priority: steps } = q.dequeue();
        const [x, y, keys] = element;
        if (keys.size === keyMap.size) {
            return steps;
        }
        for (const [key, [kx, ky]] of keyMap) {
            if (!keys.has(key)) {
                let { movesUsed, keysAcquired } = attemptToGetKey(x, y, keys, kx, ky);
                if (movesUsed) {
                    q.enqueue([kx, ky, keysAcquired], movesUsed + steps);
                }
            }
        }
    }
    return -1;
}
Shortest Path to Get All Keys