#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <fstream>

using namespace std;
typedef long long ll;

struct Node
{
	set<char> keys;
	int x, y;
	int dis;

	Node(int x, int y, set<char> keys, int dis)
	{
		this->x = x;
		this->y = y;
		this->keys = keys;
		this->dis = dis;
	}
};

vector<vector<pair<bool, set<char>>>> was;
vector<int> dx = { 0, 1, 0, -1 };
vector<int> dy = { 1, 0, -1, 0 };

bool check(int x, int y)
{
	return((y >= 0 && x >= 0) && (y < was.size() && x < was[0].size()));
}

int shortestPathAllKeys(vector<string>& grid) {
	queue<Node> q;
	was.resize(grid.size(), vector<pair<bool, set<char>>>(grid[0].size()));
	int amount_keys = 0;
	pair<int, int> spos;
	for (int i = 0; i < grid.size(); i++)
	{
		string& s = grid[i];
		for (int j = 0; j < grid[i].size(); j++)
		{
			char c = s[j];
			if (c >= 'a' && c <= 'z')
			{
				amount_keys++;
			}
			else if (c == '@')
			{
				spos = { i, j };
			}
		}
	}

	//map<char, bool> m;
	q.push(Node(spos.second, spos.first, {}, 0));
	was[spos.first][spos.second] = { true, {} };

	while (!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		set<char> keys = q.front().keys;
		int dis = q.front().dis;

		if (x == 4 && y == 2)
		{
			cout << 'aa';
		}

		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int newx = x + dx[i];
			int newy = y + dy[i];
			if (!check(newx, newy))
			{
				continue;
			}

			if (was[newy][newx].first)
			{
				bool flag = true;
				for (auto k : was[newy][newx].second)
				{
					if (keys.find(k) == keys.end())
					{
						flag = false;
						break;
					}
				}
				if (flag)
				{
					continue;
				}
			}

			char c = grid[newy][newx];
			if (c == '.')
			{
				q.push(Node(newx, newy, keys, dis + 1));
			}
			else if (c >= 'a' && c <= 'z')
			{
				keys.insert(c);
				if (keys.size() == amount_keys)
				{
					return dis + 1;
				}

				q.push(Node(newx, newy, keys, dis + 1));
			}
			else if (c >= 'A' && c <= 'Z' && keys.find(c + 32) != keys.end())
			{
				q.push(Node(newx, newy, keys, dis + 1));
			}

			was[newy][newx].first = true;
			was[newy][newx].second.insert(keys.begin(), keys.end());
		}
	}
	return -1;

}

int main()
{
	vector<string> v = {
		"@...a",
		".###A",
		"b.BCc"
	};
	cout << shortestPathAllKeys(v);
}