package baekjoon_2178_Miro_Search;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static int MAP[][] = new int[101][101];
    public static int N;
    public static int M;
    public static Queue<Vertex> queue = new LinkedList<>();
    public static Vertex start;
    public static Vertex end;

    static class Vertex {
        int x;
        int y;
        int cnt;

        public Vertex(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }

        @Override
        public boolean equals(Object obj) {
            Vertex v = (Vertex) obj;
            if (this.x == v.x && this.y == v.y) {
                return true;
            }
            return false;
        }
    }

    public static void main(String[] args) throws Exception {
        FileInputStream fis = new FileInputStream("input.txt");
        System.setIn(fis);

        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String input = st.nextToken();
            for (int j = 0; j < M; j++) {
                MAP[i][j] = Character.getNumericValue(input.charAt(j));
            }
        }

        start = new Vertex(0, 0, 1);
        queue.add(start);
        end = new Vertex(N, M, 0);
        bfs();
    }

    public static Vertex bfs() {
        while (!queue.isEmpty()) {
            Vertex v = queue.poll();
        }
        return null;
    }

    public static boolean isSafe(int x, int y) {
        return false;
    }

}

@@ -336,16 +336,71 @@
  int M;%0A
+    public static int VISITED%5B%5D%5B%5D = new int%5B101%5D%5B101%5D;%0A
     publ
@@ -1754,11 +1754,19 @@
 ex(N
-, M
+ - 1, M - 1
 , 0)
@@ -1779,14 +1779,114 @@
     
-bfs();
+Vertex result = bfs();%0A        if (result != null) %7B%0A            System.out.println(result.cnt);%0A        %7D
 %0A   
@@ -2006,106 +2006,1142 @@
     
-%7D%0A        return null;%0A    %7D%0A%0A    public static boolean isSafe(int x, int y) %7B%0A        return fals
+    if (v.equals(end)) %7B%0A                return v;%0A            %7D%0A            if (isSafe(v.x - 1, v.y) && VISITED%5Bv.x - 1%5D%5Bv.y%5D == 0) %7B%0A                VISITED%5Bv.x - 1%5D%5Bv.y%5D = 1;%0A                queue.add(new Vertex(v.x - 1, v.y, v.cnt + 1));%0A            %7D%0A            if (isSafe(v.x + 1, v.y) && VISITED%5Bv.x + 1%5D%5Bv.y%5D == 0) %7B%0A                VISITED%5Bv.x + 1%5D%5Bv.y%5D = 1;%0A                queue.add(new Vertex(v.x + 1, v.y, v.cnt + 1));%0A            %7D%0A            if (isSafe(v.x, v.y - 1) && VISITED%5Bv.x%5D%5Bv.y - 1%5D == 0) %7B%0A                VISITED%5Bv.x%5D%5Bv.y - 1%5D = 1;%0A                queue.add(new Vertex(v.x, v.y - 1, v.cnt + 1));%0A            %7D%0A            if (isSafe(v.x, v.y + 1) && VISITED%5Bv.x%5D%5Bv.y + 1%5D == 0) %7B%0A                VISITED%5Bv.x%5D%5Bv.y + 1%5D = 1;%0A                queue.add(new Vertex(v.x, v.y + 1, v.cnt + 1));%0A            %7D%0A        %7D%0A        return null;%0A    %7D%0A%0A    public static boolean isSafe(int x, int y) %7B%0A        if (x %3C 0 %7C%7C x %3E= N) %7B%0A            return false;%0A        %7D%0A        if (y %3C 0 %7C%7C y %3E= M) %7B%0A            return false;%0A        %7D%0A        if (MAP%5Bx%5D%5By%5D == 0) %7B%0A            return false;%0A        %7D%0A        return tru
 e;%0A 

implement baekjoon 2178