//import static Main.*;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    
    public static final int R = 1;
    public static final int L = -1;
    public static final int U = -4;
    public static final int D = 4;
    public static final int[] mov = new int[] {R,L,U,D};
    
    public static ArrayList<Maze> mazes = new ArrayList<>();
    
    public static void main(String[] args) {
        generateMazes("0");
        String sequence = "RRDRRDRLDRDLDLULLLDDRDDDURDRRDR";
        // execSequence(sequence);
        // int r = remaining(); // 0 if above sequence solves all mazes
        
        boolean isSolution = isSolution(sequence); // true if sequence solves all mazes
        
        System.out.println((isSolution ? "Sequence solves all " : "Sequence doesn't solve all ") + "mazes");
        
        // manualGame();
    }
    
    public static boolean isSolution(String s) {
        return mazes.size() - numberSolved(s) == 0;
    }
    
    public static int numberSolved(String s) {
        int sum = numberSolvedHard(s);
        
        for (Maze maze : mazes) {
            maze.pos = 0;
            maze.isAlive = true;
        }
        
        return sum;
    }
    
    public static int numberSolvedHard(String s) {
        int sum = 0;
        for (char c : s.toCharArray()) {
            for (Maze maze : mazes) {
                if (!maze.isAlive) continue;
                
                switch(c) {
                    case 'R': maze.move(R);
                        break;
                    case 'L': maze.move(L);
                        break;
                    case 'U': maze.move(U);
                        break;
                    case 'D': maze.move(D);
                        break;
                }
                
                if (!maze.isAlive) {
                    sum++;
                }
                
            }
        }
        
        return sum;
    }
    
    public static ArrayList<String> perms = new ArrayList<>();
    public static ArrayList<String> invrs = new ArrayList<>();
    
    public static void doPerms(ArrayList<String> cont, String seq, String move) {
        if (seq.length() >= 10)
            return;
        
        if (seq.length() >= 8)
            cont.add(seq + move);        
        
        seq += move;
        
        if (cont == perms) {
            doPerms(cont, seq, "R");
            doPerms(cont, seq, "D");
            doPerms(cont, seq, "L");            
            doPerms(cont, seq, "U");
        } else {            
            doPerms(cont, seq, "D");
            doPerms(cont, seq, "R");
            doPerms(cont, seq, "U");
            doPerms(cont, seq, "L");
        }
    }
    
    public static void execSequence(String seq) {
        for (char c : seq.toCharArray()) {
            for (Maze maze : mazes) {
                switch(c) {
                    case 'R': maze.move(R);
                        break;
                    case 'L': maze.move(L);
                        break;
                    case 'U': maze.move(U);
                        break;
                    case 'D': maze.move(D);
                        break;
                }
            }
        }
    }
    
    public static int remainingNotAtGoal(int goal) {
        int tot = remaining();
        for (Maze maze : mazes) {
            if (maze.isAlive) {
                if (maze.pos == goal) tot--;
            }
        }
        return tot;
    }
    
    public static int remaining() {
        int tot = mazes.size();
        for (Maze maze : mazes) {
            if (!maze.isAlive) tot--;
        }
        return tot;
    }
    
    public static void manualGame() {
        int r = remaining();
        
        String seq = "";
        Scanner sc = new Scanner(System.in);
        while (r > 0) {
            System.out.println("Sequence: " + seq + " Length: " + seq.length());
            System.out.println("---------------------");
            System.out.println("Removed: " + (mazes.size() - r));
            System.out.println("Remaining: " + r);
            
            int _a = 0;
            int[] a = new int[16];
            int[] p = new int[16];
            int[] d = new int[16];
            for (Maze maze : mazes) {
                if (!maze.isAlive) continue;
                
                for (int i = 0; i < 16; i++) {
                    a[i] += maze.layout[i];
                    d[i] += maze.distances[i] == 255 ? 0 : maze.distances[i];
                    _a += a[i];
                }
                
                p[maze.pos]++;
            }
            
            System.out.println("");
            System.out.printf("%-36s", "    | Obstacles");
            System.out.printf(" | Current positions\n");
            for (int i = 0; i < 4; i++) {
                System.out.print("    |    ");
                for (int j = 0; j < 4; j++) {
                    System.out.printf("%4d", a[i*4 + j]);
                    System.out.print("  ");
                }
                System.out.print("    |    ");
                for (int j = 0; j < 4; j++) {
                    System.out.printf("%4d", p[i*4 + j]);
                    System.out.print("  ");
                }
                System.out.print("    |    ");
                for (int j = 0; j < 4; j++) {
                    System.out.printf("%4d", d[i*4 + j]);
                    System.out.print("  ");
                }
                System.out.println();
            }
            System.out.println();
            System.out.print("Command: ");
            String cmd = sc.nextLine();
            seq += cmd.toUpperCase();
            
            for (Maze maze : mazes) {
                if (!maze.isAlive) continue;
                
                if (cmd.equals("d"))
                    maze.move(R);
                if (cmd.equals("a"))
                    maze.move(L);
                if (cmd.equals("w"))
                    maze.move(U);
                if (cmd.equals("s"))
                    maze.move(D);
                if (cmd.equals("p")) {
                    for (Maze m : mazes) {
                        if (m.isAlive)
                            m.printc();
                    }
                }
            }
            r = remaining();
        }
    }
    
    public static void generateMazes(String layout) {
        if (layout.length() == 16) {
            if (layout.charAt(15) == '1') return;
            
            int[] a = new int[16];
            for (int i = 0; i < 16; i++) a[i] = Character.digit(layout.charAt(i), 10);
            if (solutionExists(a, 15)) mazes.add(new Maze(a));
            return;
        }
        
        generateMazes(layout+'1');
        generateMazes(layout+'0');
    }
    
    public static boolean solutionExists(int[] a, int k) {
        if (a[0] == 2) return true;
        if (a[k] == 2) return false;
        
        for (int m : mov) {
            if (canMove(a, k, m)) {
                a[k] = 2;
                boolean f = solutionExists(a, k+m);
                a[k] = 0;
                if (f) return true;
            }
        }
        
        return false;
    }
    
    public static boolean canMove(int[] a, int pos, int dir) {
        int npos = pos + dir;
        if (npos < 0 || npos >= 16) return false;
        if (a[npos] == 1) return false;
        if (dir == 1 && pos % 4 == 3) return false;
        if (dir == -1 && pos % 4 == 0) return false;
        return Math.abs((npos - pos) % 4) <= 1;
    }
    
    public static int[] cpy(int[] arr) {
        int[] a = new int[arr.length];
        System.arraycopy(arr, 0, a, 0, a.length);
        return a;
    }
    
}

class Maze {
    
    public final int[] layout;
    
    public int[] distances;
    public int pos;
    public boolean isAlive;
    public boolean softIsAlive;
    
    public Maze(int[] layout) {
        this.layout = layout;
        this.pos = 0;
        this.isAlive = true;
    }
    
    public int getDistance() {
        return distances[pos];
    }
    
    public int getDistance(int dir) {
        if (!Main.canMove(layout, pos, dir)) return getDistance();
        return distances[pos+dir];
    }
    
    public void move(int dir) {
        int npos = pos + dir;
        if (npos < 0 || npos >= 16) return;
        if (layout[npos] == 1) return;
        if (dir == 1 && pos % 4 == 3) return;
        if (dir == -1 && pos % 4 == 0) return;
        if (Math.abs((npos - pos) % 4) > 1) return;
        
        pos = npos;
        if (pos == 15) this.isAlive = false;
    }
    
    public void print() {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++)
                System.out.printf("%-2s", i*4 + j == pos ? "x" : layout[i*4 + j]);
            System.out.println();
        }
        System.out.println();
    }
    public void printd() {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++)
                System.out.printf("%-2s", distances[i*4 + j]);
            System.out.println();
        }
        System.out.println();
    }
    
    public void printc() {
        for (int i = 0; i < 16; i++)
            System.out.print(layout[i]);
        System.out.println();
    }
}