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


public class BruteForcePath {
    static int[][] data = new int[][]{
              { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
              { 0, 1, 1, 0, 1, 1, 0, 1, 0, 0 },
              { 0, 0, 1, 0, 0, 0, 0, 1, 1, 1 },
              { 0, 0, 1, 1, 1, 1, 1, 1, 0, 0 },
              { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
            };

    private Cell[][] cells;
    private final int width;
    private final int height;

    public static void main(String[] args) {
        new BruteForcePath();
    }

    public BruteForcePath() {
        width = data[0].length;
        height = data.length;

        // Fill Cells from binary data (also transpose it, to match the style it was written)
        cells = new Cell[width][height];
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                cells[i][j] = data[j][i] == 0?new Cell(i,j):null;
            }
        }

        // Print
        printData();

        // Compute a path
        ArrayList<Cell> path = generatePath( getCellData(0,0), getCellData(width-1,height-1) );

        // Color path
        for (int i = 0; i < path.size(); i++) {
            path.get(i).path = true;
        }

        // Print
        printData();
    }

    private ArrayList<Cell> generatePath(Cell start, Cell end) {
        ArrayList<ArrayList<Cell>> paths = new ArrayList<ArrayList<Cell>>();

        // Initial path
        ArrayList<Cell> startP = new ArrayList<Cell>();
        startP.add(start);

        // Compute all paths
        ArrayList<Cell> adjacent = getAdjacentCells(start);
        for (int i = 0; i < adjacent.size(); i++) {
            ArrayList<Cell> copy = (ArrayList<Cell>) startP.clone();
            paths.add( copy );
            computePath( adjacent.get(i), end, copy, paths );
        }

        // Remove broken paths
        for (int i = 0; i < paths.size(); i++) {
            ArrayList<Cell> path = paths.get(i);
            if ( !path.get(path.size()-1).equals(end) )
                paths.remove(i--);
        }

        // Get shortest path
        int shortest = Integer.MAX_VALUE;
        ArrayList<Cell> shortestPath = null;
        for (int i = 0; i < paths.size(); i++) {
            ArrayList<Cell> path = paths.get(i);
            if ( path.size() < shortest ) {
                shortest = path.size();
                shortestPath = path;
            }
        }

        // Print
        if ( shortestPath != null ) {
            System.out.println("Shortest Path is: " + shortestPath.size() + " cell(s)");
            return shortestPath;
        }

        System.out.println("Cound not calculate path!");
        return null;
    }

    /*private ArrayList<Cell> copyPath( ArrayList<Cell> list ) {
        ArrayList<Cell> list2 = new ArrayList<Cell>();
        for (int i = 0; i < list.size(); i++) {
            list2.add(list.get(i));
        }
        return list2;
    }*/

    private void computePath(Cell current, Cell end, ArrayList<Cell> path, ArrayList<ArrayList<Cell>> paths) {
        path.add(current);
        if ( current.equals(end) )
            return;

        // Get adjacent cells
        ArrayList<Cell> adjacent = getAdjacentCells(current);

        // Remove all adjacent cells currently in path
        for (int i = 0; i < adjacent.size(); i++) {
            if ( path.contains(adjacent.get(i)) ) {
                adjacent.remove(i);
                i--;
            }
        }

        // End of path
        if ( adjacent.size() <= 0 )
            return;

        // If we're at a junction
        for (int i = 1; i < adjacent.size(); i++) {
            ArrayList<Cell> copy = (ArrayList<Cell>) path.clone();//copyPath(path);
            paths.add( copy );
            computePath( adjacent.get(i), end, copy, paths );
        }

        // Continue current path
        computePath(adjacent.get(0), end, path, paths);
    }

    private ArrayList<Cell> getAdjacentCells(Cell root) {
        ArrayList<Cell> ret = new ArrayList<Cell>();

        int xx = root.x;
        int yy = root.y;

        Cell c1 = getCellData(xx-1, yy);
        Cell c2 = getCellData(xx+1, yy);
        Cell c3 = getCellData(xx, yy-1);
        Cell c4 = getCellData(xx, yy+1);

        if ( c1 != null )
            ret.add(c1);

        if ( c2 != null )
            ret.add(c2);

        if ( c3 != null )
            ret.add(c3);

        if ( c4 != null )
            ret.add(c4);

        return ret;
    }

    private Cell getCellData(int i, int j) {
        if ( i < 0 || j < 0 || i >= width || j >= height )
            return null;
        return cells[i][j];
    }

    private void printData() {
        for (int j = 0; j < height; j++) {
            for (int i = 0; i < width; i++) {
                Cell c = cells[i][j];
                String cellSymbol = "'";
                if ( c == null )
                    cellSymbol = "#";
                if ( c != null && c.path ) {
                    cellSymbol = "*";
                }

                System.out.print( cellSymbol );
            }
            System.out.println();
        }
    }

    class Cell {
        int x;
        int y;
        boolean path;
        Cell(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}