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

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

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

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

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

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

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

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

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

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

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

class Solution {
public:

    /*
    GRAPH + BITMASKING(storing state)
    Yaha pe anyways to get min steps capturing all the keys hum use toh bfs 
    he karenge but visted mark ke liye we can'nt use the noraml way because 
    here the state is changing means the key set we have that is chaning

    hum start normal dfs se karenge but will use a visited 3-D array to store
    the state as well t[n][m][keys] yaha pe keys will be the bit represented number
    Ex we hae a,b,c keys in grid then key set will have 111 -> 3(keys)
    Ex we have a,d keys in grid then keys set will have 1001 -> 9(keys)
    
    Agar hum waapas se usse cell pe aa rahe hae and the keys we have(state) is same we will 
    not excpore that case again.
    */

    vector<vector<int> > dirs = {{0,1},{1,0},{0,-1},{-1,0}};
    int shortestPathAllKeys(vector<string>& grid) {
        int n = grid.size();
        int m = grid[0].size();

        int key_mask = 0;
        int start = 0;
        int end = 0;

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j] == '@'){
                    start = i;
                    end = j;
                }
                if(grid[i][j] >= 'a' && grid[i][j] <= 'z'){
                    key_mask = key_mask | (1 << (grid[i][j] - 'a'));
                }
            }
        }

        bool visited[n][m][key_mask + 1];
        memset(visited, false, sizeof(visited));
        queue<vector<int>> q;
        q.push({start, end, 0, 0});
        visited[start][end][0] = true;

        while(!q.empty()){
            auto v = q.front();q.pop();
            int x = v[0], y = v[1], curr_mask = v[2], step = v[3];
            if(curr_mask == key_mask) return step;
            for(auto dir : dirs){
                int xx = x + dir[0];
                int yy = y + dir[1];
                if(xx >= 0 && xx < n && yy >= 0 && yy < m && grid[xx][yy] != '#'){
                    char ch = grid[xx][yy];
                    if(!visited[xx][yy][curr_mask] && ch >= 'A' && ch <= 'Z'){
                        bool curr_lock_key = curr_mask >> (ch - 'A') & 1;
                        if(curr_lock_key){
                            q.push({xx,yy,curr_mask,step+1});
                            visited[xx][yy][curr_mask] = true;
                        }
                    }else if(ch >= 'a' && ch <= 'z'){
                        int new_mask = curr_mask | (1 << (ch - 'a'));
                        if(!visited[xx][yy][new_mask]){
                            q.push({xx,yy,new_mask,step+1});
                            visited[xx][yy][new_mask] = true;
                        }
                    }else{
                        if(!visited[xx][yy][curr_mask]){
                            q.push({xx,yy,curr_mask,step+1});
                            visited[xx][yy][curr_mask] = true;
                        }
                    }
                }
            }
        }

        return -1;
    }
};
55759