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

struct cell_hash {
    size_t operator()(const std::pair<int, int>& p) const
    {
        // Hash the first element
        size_t first_hash = std::hash<int>{}(p.first);
        // Hash the second element
        size_t second_hash = std::hash<int>{}(p.second);
        // Combine the two hash values
        return first_hash ^ (second_hash + 0x9e3779b9 + (first_hash << 6) + (second_hash >> 2));
    }
};

using grid = std::vector<std::string>;
using cell = std::pair<int, int>;
using dir = std::vector<std::pair<int, int>>;
using vi = std::vector<std::vector<bool>>;
using dist = std::vector<std::vector<int>>;
using memo = std::unordered_map<cell, std::unordered_map<int, int>, cell_hash>;

class Solution {
private:
    const int inf = 5 * 1e+05;
    const char PLAYER = '@';
    const char WALL = '#';
    const char EMPTY = '.';
    int M, N, K = 0;
    dir dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    bool checkBoundary(int r, int c)
    { return r >= 0 && r < M && c >= 0 && c < N; }
    bool isLock(const char& c) { return std::isalpha(c) && std::isupper(c); }
    int keyToInt(const char& key) { return (int)key - 97; }
    int lockToInt(const char& lock) { return (int)lock - 65; }
    int bfs(const grid& g, const cell& source, const cell& sink, int obtained_keys)
    {
        dist distance = dist(M, std::vector<int>(N, inf));
        vi visited = vi(M, std::vector<bool>(N, false));
        std::queue<cell> q;
        visited[source.first][source.second] = true;
        distance[source.first][source.second] = 0;
        q.push(source);
        bool finished = false;
        while(!q.empty() && !finished)
        {
            auto v = q.front();
            q.pop();
            int c_r = v.first;
            int c_c = v.second;
            if(v.first == sink.first && 
               v.second == sink.second)
            {
                finished = true;
                break;
            }
            for(auto d : dirs)
            {
                int r = c_r + d.first;
                int c = c_c + d.second;
                if(!checkBoundary(r, c) ||
                   g[r][c] == WALL ||
                   visited[r][c] ||
                   (isLock(g[r][c]) &&
                    !(obtained_keys & (1 << lockToInt(g[r][c])))))
                  continue;

                visited[r][c] = true;
                distance[r][c] = distance[c_r][c_c] + 1;
                q.push({r, c});
            }
        }
        return distance[sink.first][sink.second];
    }
    int calculateMinPath(const grid& g, const cell& source, const std::unordered_map<int, cell>& keys, int mask, memo& mt) 
    {
        if(mask == ((1 << K) - 1))
            return 0;

        if(auto it_f = mt.find(source); it_f != mt.end())
          if(auto it_s = (*it_f).second.find(mask); it_s != (*it_f).second.end())
            return (*it_s).second;

        int path = inf;
        for(int k = 0; k < K; k++)
        {
            if((mask & (1 << k)))
              continue;
            auto it = keys.find(k);
            if(auto it = keys.find(k); it != keys.end())
            {
                int res = bfs(g, source, (*it).second, mask);
                if(res != inf)
                  path = std::min(path, res + calculateMinPath(g, (*it).second, keys, (mask | (1 << k)), mt));
            }
        }
        return mt[source][mask] = path;
    }
public:
    int shortestPathAllKeys(vector<string>& g) 
    {
        M = g.size();
        N = g[0].size();
        std::unordered_map<int, cell> keys;
        cell player; // player's initial position
        for(int r = 0; r < M; r++)
          for(int c = 0; c < N; c++)
          {
             if(std::isalpha(g[r][c]) && 
                std::islower(g[r][c]))
            {
               K++;
               keys[keyToInt(g[r][c])] = {r, c};
            }
             if(g[r][c] == PLAYER)
               player = {r, c};  
          }
        memo mt;  
        int ans = calculateMinPath(g, player, keys, 0, mt);
        return ans == inf ? -1 : ans;    
    }
};
62261