import java.util.LinkedList;

class Solution {
    class Node implements Comparable<Node> {
        int keys;
        int step;
        int y;
        int x;

        Node(int keys, int step, int y, int x) {
            this.keys = keys;
            this.step = step;
            this.y = y;
            this.x = x;
        }
    }

    int m;
    int n;
    int acc;
    char[][] map;

    final int[] dy = new int[]{0, 1, 0, -1};
    final int[] dx = new int[]{1, 0, -1, 0};

    public int shortestPathAllKeys(String[] grid) {
        if ((m = grid.length) == 0 || (n = grid[0].length()) == 0) return -1;
        LinkedList<Node> queue = new LinkedList<>();
        map = new char[m][n];
        for (int i = 0; i < m; i++) {
            map[i] = grid[i].toCharArray();
            for (int j = 0; j < n; j++) {
                char ch = map[i][j];
                if (ch == '@') queue.offer(new Node(0, 0, i, j));
                if ('a' <= ch && ch <= 'f') acc |= 1 << (ch - 'a');
            }
        }
        boolean[][][] used = new boolean[m][n][1 << 6];
        while (!queue.isEmpty()) {
            Node top = queue.poll();
            if (!isValidMove(top, used)) continue;
            used[top.y][top.x][top.keys] = true;
            char ch = map[top.y][top.x];
            if ('a' <= ch && ch <= 'f') top.keys |= 1 << (ch - 'a');
            if (top.keys == acc) return top.step;
            for (int i = 0; i < 4; i++) {
                Node next = new Node(top.keys, top.step + 1, top.y + dy[i], top.x + dx[i]);
                queue.offer(next);
            }
        }
        return -1;
    }

    private boolean isValidMove(Node node, boolean[][][] used) {
        if (node.y < 0 || m <= node.y || node.x < 0 || n <= node.x) return false; // Out of map
        if (used[node.y][node.x][node.keys]) return false; // Visited
        char ch = map[node.y][node.x];
        if (ch == '#') return false; // Wall
        if ('A' <= ch && ch <= 'F') return ((1 << (ch - 'A')) & node.keys) != 0; // Has no key
        return true;
    }
}