import java.io.IOException; import java.nio.file.Paths; import java.util.*; class Pair { int x; int y; public Pair(int x, int y) { this.x = x; this.y = y; } } public class Main { static int SIZE = 50; static ArrayList> naapurit = new ArrayList<>(SIZE*SIZE +1); static Random rng = new Random(); private static final ArrayList empty=new ArrayList<>(); public static void main(String[] args) throws IOException { Scanner scanner = new Scanner(Paths.get("input.txt")); for (int i = 0; i < SIZE*SIZE+1; i++) { naapurit.add(new HashSet<>()); } while (scanner.hasNextLine()) { String line = scanner.nextLine(); String[] parts = line.split(" "); int last = -1; for (String part : parts) { int ipart = Integer.parseInt(part); if (last != -1) { naapurit.get(last).add(ipart); naapurit.get(ipart).add(last); } last = ipart; } } for (int i = 0; i < naapurit.size(); i++) { HashSet integers = naapurit.get(i); if (integers.isEmpty()) { empty.add(i); } } solve(); } static int tryOne(int number, int x, int y) { boolean b1 = insideBounds(x, y); if (!b1) { return -1; } boolean b = canBePlacedBasicRules(number, x, y); boolean b2 = canBePlaced(number, x, y); if (b && b2) one(number, x, y); if (!b2 && b) { return -3; } if (b) { return 0; } return -2; } static ArrayList order = new ArrayList<>(); static void one(int number, int x, int y) { HashSet set = naapurit.get(number); if (set.isEmpty()) { return; } added.put(number, new Pair(x,y)); order.add(number); ruudukko[y][x] = number; if (added.size() >= SIZE*SIZE-empty.size()) { throw new IllegalArgumentException("OH MY GOD!!!"); } for (Integer integer : set) { int b = tryOne(integer,x+1,y); int b2 = tryOne(integer,x-1,y); int b3 = tryOne(integer,x,y+1); int b4 = tryOne(integer,x,y-1); if ((b<0 && b2 <0 && b3<0 && b4 < 0) && (b == -3 | b2 ==-3 | b3==-3 | b4==-3)) { int index = order.indexOf(number); //System.out.println("Removing "+index+" "+order.size()+" "+number+" "+integer); for (int i = order.size()-1; i >= index; i = order.size()-1) { int num = order.get(i); Pair pair = added.get(num); added.remove(num); ruudukko[pair.y][pair.x] = 0; order.remove(order.size()-1); } return; } } if (!naapuritPaikallaan(number,x,y)) { int index = order.indexOf(number); for (int i = order.size()-1; i >= index; i = order.size()-1) { int num = order.get(i); Pair pair = added.get(num); added.remove(num); ruudukko[pair.y][pair.x] = 0; order.remove(order.size()-1); } } } static boolean naapuritPaikallaan(int number,int x,int y) { Set naap = naapurit.get(number); ArrayList ruudut = new ArrayList<>(); ruudut.add(getRuutu(x+1,y)); ruudut.add(getRuutu(x-1,y)); ruudut.add(getRuutu(x,y+1)); ruudut.add(getRuutu(x,y-1)); for (Integer integer : naap) { if (!ruudut.contains(integer)) { return false; } } return true; } static int getRuutu(int x, int y) { if (!insideBounds(x,y)) { return 0; } return ruudukko[x][y]; } static boolean insideBounds(int x, int y) { return !(x > SIZE - 1 | x < 0 | y > SIZE - 1 | y < 0); } static boolean canBePlacedBasicRules(int number, int x, int y) { return !added.containsKey(number) && ruudukko[y][x] == 0; } static boolean canBePlaced(int number, int x, int y) { for (Integer integer : added.keySet()) { if (naapurit.get(integer).contains(number) && added.containsKey(integer)) { if (!isNear(added.get(integer),x,y)) { return false; } } } return mahdollistaLaittaaKaikkiNaapurit(naapurit.get(number),x,y); } static int test(int x, int y,Set set) { if (!insideBounds(x,y)) { return 0; } int r = ruudukko[y][x]; if (r== 0) { return 1; } if (set.contains(r)) { return 1; } return 0; } static boolean mahdollistaLaittaaKaikkiNaapurit(Set set, int x,int y) { int tila = 0; tila += test(x+1,y,set); tila += test(x-1,y,set); tila += test(x,y+1,set); tila += test(x,y-1,set); return tila >= set.size(); } static void print(int[][] ar) { for (int[] ints : ar) { for (int anInt : ints) { System.out.println(anInt+" "); } System.out.print("\n"); } } static boolean isNear(Pair pair,int x,int y) { boolean xsame = (pair.x == x+1 | pair.x == x-1) && y==pair.y; boolean ysame = (pair.y == y+1 | pair.y == y-1) && x==pair.x; return xsame ^ ysame; } static int[][] ruudukko = new int[SIZE][SIZE]; static HashMap added = new HashMap<>(); private static void solve() { int l = 10000; while (l > 0) { l--; try { one(rng.nextInt(SIZE*SIZE-1)+1,rng.nextInt(SIZE),rng.nextInt(SIZE)); } catch (IllegalArgumentException e) { int i = 0; for (int[] ints : ruudukko) { for (int j = 0; j < ints.length; j++) { if (ints[j] == 0) { ints[j] = empty.get(i); i++; } } } print(ruudukko); break; } } } }