import java.util.*;
import java.io.*;

class Point{
    public int x;
    public int y;
    public Point(){
        x = 0;
        y = 0;
    }
    public Point (int x, int y){
        this.x = x;
        this.y = y;
    }
    public void print(){
        System.out.println("X = "+x+" Y = "+y);
    }

    public double jarakDuaTitik(Point b){
        return (Math.sqrt(((this.x-b.x)*(this.x-b.x))+((this.y-b.y)*(this.y-b.y))));
    }
}

class Node{
    public ArrayList<Point> P;
    public double cost;

    public Node(){
        this.P = new ArrayList<Point>();
        this.cost = 0;
    }

    public void copyNode(Node N){
        for (int i = 0;i<N.P.size();i++){
            P.add(N.P.get(i));
        }
    }
}

class labirin{
    public boolean[][] matriks;
    public Point start;
    public int baris;
    public int kolom;
    public int[][] matriksInt;
    public ArrayList<Point> currentList;
    public Node currentNode;

    public labirin(int baris, int kolom){
        this.baris = baris;
        this.kolom = kolom;
        matriks = new boolean[baris][kolom];
        matriksInt = new int[baris][kolom];
        start = new Point();
        currentList = new ArrayList<Point>();
        currentNode = new Node();
    }

    public void printLabirin(){
        for (int i = 0;i< baris;i++){
            for (int j = 0;j<kolom;j++){
                if (matriks[i][j] == true){
                    System.out.print("1");
                }else{
                    System.out.print("0");
                }
            }
            System.out.println();
        }
    }

    public void transferMatriks(){
        int i,j;
        for(i = 0;i<baris;i++){
            for(j = 0;j<kolom;j++){
                if (matriks[i][j]){
                    matriksInt[i][j] = 1;
                }else{
                    matriksInt[i][j] = 0;
                }
            }
        }
    }

    public void findStart(){
        boolean found = false;
        int i = 0;
        while ((!found)&&(i<kolom)){
            if (!matriks[0][i]){
                start.x = i;
                start.y = 0;
                found = true;
            }
            if ((!matriks[baris-1][i])&&(!found)){
                start.x = i;
                start.y = baris-1;
                found = true;
            }
            i++;
        }
        i = 0;
        while ((!found)&&(i<baris)){
            if (!matriks[i][0]){
                start.x = 0;
                start.y = i;
                found = true;
            }
            if ((!matriks[i][kolom-1])&&(!found)){
                start.x = kolom-1;
                start.y = i;
                found = true;
            }
            i++;
        }
    }

    public void copyList(ArrayList<Point> dari, ArrayList<Point> ke){
        for (int i = 0;i<dari.size();i++){
            ke.add(dari.get(i));
        }
    }

    public void solveBFS(){ //Menyelesaikan dengan algoritma BFS
        currentList.clear();
        ArrayList<ArrayList<Point>> queue = new ArrayList<ArrayList<Point>>();
        Point currentPoint = new Point(start.x, start.y);
        boolean[][] matriksSudahDikunjungi = new boolean[baris][kolom];
        matriksSudahDikunjungi[start.y][start.x] = true;
        currentList.add(currentPoint);
        if (currentPoint.x == 0){
            currentList.add(new Point(currentPoint.x+1,currentPoint.y));
        }
        if (currentPoint.x == kolom-1){
            currentList.add(new Point(currentPoint.x-1,currentPoint.y));
        }
        if (currentPoint.y == 0){
            currentList.add(new Point(currentPoint.x,currentPoint.y+1));
        }
        if (currentPoint.y == baris-1){
            currentList.add(new Point(currentPoint.x,currentPoint.y-1));
        }
        currentPoint = currentList.get(currentList.size()-1);
        while ((currentPoint.x!=0)&&(currentPoint.x!=kolom-1)&&(currentPoint.y!=0)&&(currentPoint.y!=baris-1)){
            matriksSudahDikunjungi[currentPoint.y][currentPoint.x] = true;
            if (!matriks[currentPoint.y][currentPoint.x+1]){
                if(!matriksSudahDikunjungi[currentPoint.y][currentPoint.x+1]){
                    ArrayList<Point> prevList = new ArrayList<Point>();
                    copyList(currentList,prevList);
                    prevList.add(new Point(currentPoint.x+1,currentPoint.y));
                    queue.add(prevList);
                }
            }
            if (!matriks[currentPoint.y][currentPoint.x-1]){
                if(!matriksSudahDikunjungi[currentPoint.y][currentPoint.x-1]){
                    ArrayList<Point> prevList = new ArrayList<Point>();
                    copyList(currentList,prevList);
                    prevList.add(new Point(currentPoint.x-1,currentPoint.y));
                    queue.add(prevList);
                }
            }
            if (!matriks[currentPoint.y+1][currentPoint.x]){
                if(!matriksSudahDikunjungi[currentPoint.y+1][currentPoint.x]){
                    ArrayList<Point> prevList = new ArrayList<Point>();
                    copyList(currentList,prevList);
                    prevList.add(new Point(currentPoint.x,currentPoint.y+1));
                    queue.add(prevList);
                }
            }
            if (!matriks[currentPoint.y-1][currentPoint.x]){
                if(!matriksSudahDikunjungi[currentPoint.y-1][currentPoint.x]){
                    ArrayList<Point> prevList = new ArrayList<Point>();
                    copyList(currentList,prevList);
                    prevList.add(new Point(currentPoint.x,currentPoint.y-1));
                    queue.add(prevList);
                }
            }
            currentList = queue.get(0);
            currentPoint = currentList.get(currentList.size()-1);
            queue.remove(0);
        }
    }

    public Point findFinish(){
        Point pointTemp = new Point();
        boolean found = false;
        int i = 0;
        while ((!found)&&(i<kolom)){
            if (!matriks[0][i]&&((i!=start.x)||(start.y!=0))){
                pointTemp.x = i;
                pointTemp.y = 0;
                found = true;
            }
            if ((!matriks[baris-1][i])&&(!found)&&((i!=start.x)||(start.y!=baris-1))){
                pointTemp.x = i;
                pointTemp.y = baris-1;
                found = true;
            }
            i++;
        }
        i = 0;
        while ((!found)&&(i<baris)){
            if ((!matriks[i][0])&&((0!=start.x)||(start.y!=i))){
                pointTemp.x = 0;
                pointTemp.y = i;
                found = true;
            }
            if ((!matriks[i][kolom-1])&&(!found)&&((kolom-1!=start.x)||(start.y!=i))){
                pointTemp.x = kolom-1;
                pointTemp.y = i;
                found = true;
            }
            i++;
        }
        return pointTemp;
    }

    public void solveAStar(){   //Menyelesaikan dengan algoritma A*
        int fh = 0,idxMin;
        currentNode.P.clear();
        boolean[][] matriksSudahDikunjungi = new boolean[baris][kolom];
        Point finishPoint = new Point();
        finishPoint = findFinish();
        ArrayList<Node> arrayNode = new ArrayList<Node>();
        currentNode.P.add(new Point(start.x,start.y));
        currentNode.cost = fh + currentNode.P.get(currentNode.P.size()-1).jarakDuaTitik(finishPoint);// Ini adalah fungsi cost-nya
        matriksSudahDikunjungi[currentNode.P.get(currentNode.P.size()-1).y][currentNode.P.get(currentNode.P.size()-1).x] = true;

        if (currentNode.P.get(currentNode.P.size()-1).x == 0){
            currentNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x+1,currentNode.P.get(currentNode.P.size()-1).y));
        }
        if (currentNode.P.get(currentNode.P.size()-1).x == kolom-1){
            currentNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x-1,currentNode.P.get(currentNode.P.size()-1).y));
        }
        if (currentNode.P.get(currentNode.P.size()-1).y == 0){
            currentNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x,currentNode.P.get(currentNode.P.size()-1).y+1));
        }
        if (currentNode.P.get(currentNode.P.size()-1).y == baris-1){
            currentNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x,currentNode.P.get(currentNode.P.size()-1).y-1));
        }


        while ((currentNode.P.get(currentNode.P.size()-1).x!=finishPoint.x)||(currentNode.P.get(currentNode.P.size()-1).y!=finishPoint.y)){
            fh++;
            matriksSudahDikunjungi[currentNode.P.get(currentNode.P.size()-1).y][currentNode.P.get(currentNode.P.size()-1).x] = true;
            if (!matriks[currentNode.P.get(currentNode.P.size()-1).y][currentNode.P.get(currentNode.P.size()-1).x+1]){
                if(!matriksSudahDikunjungi[currentNode.P.get(currentNode.P.size()-1).y][currentNode.P.get(currentNode.P.size()-1).x+1]){
                    Node nextNode = new Node();
                    nextNode.copyNode(currentNode);
                    nextNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x+1,currentNode.P.get(currentNode.P.size()-1).y));
                    nextNode.cost = fh + nextNode.P.get(currentNode.P.size()-1).jarakDuaTitik(finishPoint);
                    arrayNode.add(nextNode);

                }
            }
            if (!matriks[currentNode.P.get(currentNode.P.size()-1).y][currentNode.P.get(currentNode.P.size()-1).x-1]){
                if(!matriksSudahDikunjungi[currentNode.P.get(currentNode.P.size()-1).y][currentNode.P.get(currentNode.P.size()-1).x-1]){
                    Node nextNode = new Node();
                    nextNode.copyNode(currentNode);
                    nextNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x-1,currentNode.P.get(currentNode.P.size()-1).y));
                    nextNode.cost = fh + nextNode.P.get(currentNode.P.size()-1).jarakDuaTitik(finishPoint);
                    arrayNode.add(nextNode);

                }
            }
            if (!matriks[currentNode.P.get(currentNode.P.size()-1).y+1][currentNode.P.get(currentNode.P.size()-1).x]){
                if(!matriksSudahDikunjungi[currentNode.P.get(currentNode.P.size()-1).y+1][currentNode.P.get(currentNode.P.size()-1).x]){
                    Node nextNode = new Node();
                    nextNode.copyNode(currentNode);
                    nextNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x,currentNode.P.get(currentNode.P.size()-1).y+1));
                    nextNode.cost = fh + nextNode.P.get(currentNode.P.size()-1).jarakDuaTitik(finishPoint);
                    arrayNode.add(nextNode);
                }
            }
            if (!matriks[currentNode.P.get(currentNode.P.size()-1).y-1][currentNode.P.get(currentNode.P.size()-1).x]){
                if(!matriksSudahDikunjungi[currentNode.P.get(currentNode.P.size()-1).y-1][currentNode.P.get(currentNode.P.size()-1).x]){
                    Node nextNode = new Node();
                    nextNode.copyNode(currentNode);
                    nextNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x,currentNode.P.get(currentNode.P.size()-1).y-1));
                    nextNode.cost = fh + nextNode.P.get(currentNode.P.size()-1).jarakDuaTitik(finishPoint);
                    arrayNode.add(nextNode);
                }
            }
            idxMin = 0;
            for (int i = 1;i<arrayNode.size();i++){
                if (arrayNode.get(i).cost<arrayNode.get(idxMin).cost){
                    idxMin = i;
                }
            }
            currentNode = arrayNode.get(idxMin);
            arrayNode.remove(idxMin);
        }

        currentNode.P.get(currentNode.P.size()-1).print(); //currentNode yg skr ini titik akhirnya
    }

    public static void main(String args[]){
        BufferedReader br = null,br2 = null;
        FileReader fr = null,fr2 = null;
        String namaFile;
        Scanner scan = new Scanner(System.in);
        System.out.print("Input nama file : ");
        namaFile = scan.nextLine();
        scan.close();
        try{
            fr = new FileReader(namaFile);
            br = new BufferedReader(fr);

            int x,y,i;
            String sCurrentLine = br.readLine();
            x = sCurrentLine.length();
            y = 0;
            while(sCurrentLine!=null){
                y++;
                sCurrentLine = br.readLine();
            }
            System.out.println("Jumlah Baris : "+y);
            System.out.println("Jumlah Kolom : "+x);
            System.out.println();

            labirin objLabirin = new labirin(y,x);

            fr2 = new FileReader(namaFile);
            br2 = new BufferedReader(fr2);
            y = 0;
            sCurrentLine = br2.readLine();
            while(sCurrentLine!=null){
                i = 0;
                while(i<x){
                    if (sCurrentLine.charAt(i)=='0'){
                        objLabirin.matriks[y][i] = false;
                    }else{
                        objLabirin.matriks[y][i] = true;
                    }
                    i++;
                }
                y++;
                sCurrentLine = br2.readLine();
            }
            objLabirin.transferMatriks();
            objLabirin.printLabirin();
            objLabirin.findStart();
            System.out.println();
            System.out.println();
        }
        catch (IOException e) {
            e.printStackTrace();
            System.out.println("Ada kesalahan pada file eksternal.");
        }
        finally {
            try {
                if (br != null)
                    br.close();
                if (fr != null)
                    fr.close();
            } catch (IOException ex) {
                ex.printStackTrace();
            }
        }
    }
}