fork download 
  1. import java.util.ArrayList;
  2.  
  3. class Maze { 
  4. 	Maze(int[] stuff) {}
  5. };
  6.  
  7. class Main {
  8.  
  9.     public static final int R = 1;
  10.     public static final int L = -1;
  11.     public static final int U = -4;
  12.     public static final int D = 4;
  13.     public static final int[] mov = new int[] {R,L,U,D};
  14.  
  15.     public static int remaining = 0;
  16.  
  17.     public static ArrayList<Maze> mazes = new ArrayList<>();
  18.  
  19.     public static void main(String[] arg) {
  20.         generateMazes("0");
  21.         System.out.println(mazes.size());
  22.     }
  23.  
  24.     public static boolean solutionExists(int[] a, int k) {
  25.         if (a[0] == 2) return true;
  26.         if (a[k] == 2) return false;
  27.  
  28.         for (int m : mov) {
  29.             if (canMove(a, k, m)) {
  30.                 a[k] = 2;
  31.                 boolean f = solutionExists(a, k+m);
  32.                 a[k] = 0;
  33.                 if (f) return true;
  34.             }
  35.         }
  36.  
  37.         return false;
  38.     }
  39.  
  40.     public static void generateMazes(String layout) {
  41.         if (layout.length() == 16) {
  42.             if (layout.charAt(15) == '1') return;
  43.  
  44.             int[] a = new int[16];
  45.             for (int i = 0; i < 16; i++) a[i] = Character.digit(layout.charAt(i), 10);
  46.             if (solutionExists(a, 15)) mazes.add(new Maze(a));
  47.             return;
  48.         }
  49.  
  50.         generateMazes(layout+'1');
  51.         generateMazes(layout+'0');
  52.     }
  53.  
  54.     public static boolean canMove(int[] a, int pos, int dir) {
  55.         int npos = pos + dir;
  56.         if (npos < 0 || npos >= 16) return false;
  57.         if (a[npos] == 1) return false;
  58.         if (dir == 1 && pos % 4 == 3) return false;
  59.         if (dir == -1 && pos % 4 == 0) return false;
  60.  
  61.         return Math.abs((npos - pos) % 4) <= 1;
  62.     }
  63.  
  64. }
Success #stdin #stdout 0.11s 380224KB
comments (?)
stdin 
Standard input is empty
stdout 
3828
https://ideone.com/i42KG9
language:
Java (12.0.1)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!