import java.util.*;
import java.awt.Point;

public class Labyrintti {

    public ArrayDeque<Solmu> jono = new ArrayDeque<>();
    public ArrayList<Solmu> vieruslista = new ArrayList<>();
    public HashMap<String, Boolean> ovet = new HashMap<>();
    ArrayList<Character> doors;
    ArrayList<String> collectedKeys;
    public boolean[][] vierailtu;
    public int[][] etaisyys;
    public Solmu[][] edeltaja;
    public Point alku;

    public String etsi(char[][] laby) {
        vierailtu = new boolean[laby.length][laby[0].length];

        etaisyys = new int[laby.length][laby[0].length];
        for (int x = 0; x < vierailtu.length; x++) {
            for (int y = 0; y < vierailtu[x].length; y++) {
                vierailtu[x][y] = false;
                etaisyys[x][y] = Integer.MAX_VALUE;
            }
        }
        doors = new ArrayList<>();
        doors.add('A');
        doors.add('B');
        doors.add('C');
        doors.add('D');
        ArrayList<Character> keys = new ArrayList<>();
        keys.add('a');
        keys.add('b');
        keys.add('c');
        keys.add('d');
        collectedKeys = new ArrayList<>();
        edeltaja = new Solmu[laby.length][laby[0].length];
        ArrayList<Point> reitti = new ArrayList<>();
        Solmu alku = new Solmu(findPoint(laby, 'x'), collectedKeys, reitti);

        jono.addLast(alku);
        vierailtu[alku.getCoordinates().y][alku.getCoordinates().x] = true;
        etaisyys[alku.getCoordinates().y][alku.getCoordinates().x] = 0;
        boolean yFound = false;
        while (!jono.isEmpty() && !yFound) {
            vieruslista.clear();
            Solmu solmu = jono.pop();
            addNeighbours(laby, solmu);
            for (Solmu naapuri : vieruslista) {
                char curNeighbor = laby[naapuri.getCoordinates().y][naapuri.getCoordinates().x];
                yFound = (curNeighbor == 'y');
                if (yFound) {
                    edeltaja[naapuri.getCoordinates().y][naapuri.getCoordinates().x] = solmu;
                    vierailtu[naapuri.getCoordinates().y][naapuri.getCoordinates().x] = true;
                    break;
                }
                if (keys.contains(laby[naapuri.getCoordinates().y][naapuri.getCoordinates().x]) && !collectedKeys.contains(laby[naapuri.getCoordinates().y][naapuri.getCoordinates().x])) {
                    String key = String.valueOf(laby[naapuri.getCoordinates().y][naapuri.getCoordinates().x]);
                    collectedKeys.add(key);
                    for (int x = 0; x < vierailtu.length; x++) {
                        for (int y = 0; y < vierailtu[x].length; y++) {
                            if (vierailtu[x][y]) {
                                vierailtu[x][y] = false;
                            }
                        }
                    }
                }
                vierailtu[naapuri.getCoordinates().y][naapuri.getCoordinates().x] = true;
                jono.addLast(naapuri);
                etaisyys[naapuri.getCoordinates().y][naapuri.getCoordinates().x] = etaisyys[solmu.getCoordinates().y][solmu.getCoordinates().x] + 1;
                edeltaja[naapuri.getCoordinates().y][naapuri.getCoordinates().x] = solmu;
            }
        }
        Solmu loppu = new Solmu(findPoint(laby, 'y'), collectedKeys, reitti);
        if (!vierailtu[loppu.getCoordinates().y][loppu.getCoordinates().x]) {
            return null;
        }
        String polku = "";
        System.out.println(loppu.getReitti().size());
        System.out.println(loppu.getReitti());
        ArrayList<Point> s = loppu.getReitti();
        for (int i = 1; i < s.size(); i++) {
            Point currCoord = s.get(i);
            Point prevCoord = s.get(i - 1);
            if (prevCoord.x == currCoord.x + 1) {
                polku = polku + "O";
            } else if (prevCoord.x == currCoord.x - 1) {
                polku = polku + "V";
            } else if (prevCoord.y == currCoord.y - 1) {
                polku = polku + "A";
            } else if (prevCoord.y == currCoord.y + 1) {
                polku = polku + "Y";
            }
        }
        return polku;
    }

    public void addNeighbours(char[][] array, Solmu solmu) {
        Character m = array[solmu.getCoordinates().y - 1][solmu.getCoordinates().x];
        if (m != '#') {
            if (((doors.contains(m) && collectedKeys.contains(String.valueOf(m).toLowerCase())) || !doors.contains(m)) && !vierailtu[solmu.getCoordinates().y - 1][solmu.getCoordinates().x]) {
                Point point = new Point(solmu.getCoordinates().x, solmu.getCoordinates().y - 1);
                vieruslista.add(new Solmu(point, collectedKeys, solmu.getReitti()));
            }
        }
        //m = array[solmu.getCoordinates().x + 1][solmu.getCoordinates().y];
        m = array[solmu.getCoordinates().y + 1][solmu.getCoordinates().x];
        if (m != '#') {
            if (((doors.contains(m) && collectedKeys.contains(String.valueOf(m).toLowerCase())) || !doors.contains(m)) && !vierailtu[solmu.getCoordinates().y + 1][solmu.getCoordinates().x]) {
                Point point = new Point(solmu.getCoordinates().x, solmu.getCoordinates().y + 1);
                vieruslista.add(new Solmu(point, collectedKeys, solmu.getReitti()));
            }
        }
        //m = array[solmu.getCoordinates().x][solmu.getCoordinates().y - 1];
        m = array[solmu.getCoordinates().y][solmu.getCoordinates().x + 1];
        if (m != '#') {
            if (((doors.contains(m) && collectedKeys.contains(String.valueOf(m).toLowerCase())) || !doors.contains(m)) && !vierailtu[solmu.getCoordinates().y][solmu.getCoordinates().x + 1]) {
                Point point = new Point(solmu.getCoordinates().x + 1, solmu.getCoordinates().y);
                vieruslista.add(new Solmu(point, collectedKeys, solmu.getReitti()));
            }
        }
        //m = array[solmu.getCoordinates().x][solmu.getCoordinates().y + 1];
        m = array[solmu.getCoordinates().y][solmu.getCoordinates().x - 1];
        if (m != '#') {
            if (((doors.contains(m) && collectedKeys.contains(String.valueOf(m).toLowerCase())) || !doors.contains(m)) && !vierailtu[solmu.getCoordinates().y][solmu.getCoordinates().x - 1]) {
                Point point = new Point(solmu.getCoordinates().x - 1, solmu.getCoordinates().y);
                vieruslista.add(new Solmu(point, collectedKeys, solmu.getReitti()));
            }
        }
    }

    public Point findPoint(char[][] array, char x) {
        Point location = new Point(0, 0);
        for (int row = 0; row < array.length; row++) {
            for (int col = 0; col < array[0].length; col++) {
                if (array[row][col] == x) {
                    location.y = row;
                    location.x = col;
                    break;
                }
            }
        }
        return location;
    }

}
_____________________________________________________________________________________________________________________________


import java.awt.Point;
import java.util.ArrayList;


public class Solmu {

    private Point koordinaatit;
    private ArrayList<String> avaimet;
    private ArrayList<Point> reitti = new ArrayList<>();

    public Solmu(Point koordinaatit, ArrayList<String> avaimet, ArrayList<Point> reitti){
        this.koordinaatit = koordinaatit;
        this.avaimet = avaimet;
        this.reitti = reitti;
        this.koordinaatit = koordinaatit;
        this.reitti.add(this.koordinaatit);
    }

    public ArrayList<Point> getReitti(){
        return reitti;
    }

    public Point getCoordinates(){
        return this.koordinaatit;
    }
}
_________________________________________________________________________________________________________________________________


import java.util.*;

public class Main {

    public static void main(String[] args) {
        Labyrintti l = new Labyrintti();
        char[][] t =   {{'#', '#', '#', '#', '#', '#', '#'},
                        {'#', 'x', '#', '.', 'y', 'b', '#'},
                        {'#', '.', '#', 'A', '#', '#', '#'},
                        {'#', 'b', 'B', '.', 'B', 'a', '#'},
                        {'#', '#', '#', '#', '#', '#', '#'}};
        System.out.println(l.etsi(t)); // AAOOOOVVYYO

//        Labyrintti k = new Labyrintti();
////        char[][] y = {{'#','#','#','#','#','#','#'},
////                      {'#','x','#','B','y','b','#'},
////                      {'#','.','#','A','#','#','#'},
////                      {'#','b','.','.','.','a','#'},
////                      {'#','#','#','#','#','#','#'}};
//        System.out.println(k.etsi(y)); // AAOOOOVVYYO
    }
}