백준_2178(BFS)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
static Scanner sc = new Scanner(System.in);
static int n = sc.nextInt();
static int m = sc.nextInt();
static int[][] arr = new int[100+1][100+1];
static int[][] visited = new int[100+1][100+1];
static int[][] arr2 = new int[100+1][100+1];

public static boolean check(int y,int x) {
	if(y<0 || x<0 || y>n-1 || x>m-1)return false;
	if(arr[y][x]==0)
		return false;
	if(visited[y][x]==1)
		return false;
	return true;
}

public static void main(String[] args) {
  Queue<Integer> qx = new LinkedList<Integer>();
	Queue<Integer> qy = new LinkedList<Integer>();
	for(int i=0;i<n;i++) {
		String temp = sc.next();
		for(int j=0;j<m;j++) {
			arr[i][j]=Integer.parseInt(temp.charAt(j)+"");
		}
	}
	
	qx.offer(0);qy.offer(0);arr2[0][0]=1;
	while(!qy.isEmpty()&&!qx.isEmpty()) {
		int x = qx.poll(); int y = qy.poll(); int loc = arr2[y][x];

		if(check(y-1,x)) {
			qy.offer(y-1); qx.offer(x); arr2[y-1][x] = loc+1;visited[y-1][x] = 1;
		}
		if(check(y,x+1)) {
			qy.offer(y); qx.offer(x+1); arr2[y][x+1] = loc+1;visited[y][x+1] = 1;
		}
		if(check(y+1,x)) {
			qy.offer(y+1); qx.offer(x); arr2[y+1][x] = loc+1;visited[y+1][x] = 1;
		}
		if(check(y,x-1)) {
			qy.offer(y); qx.offer(x-1); arr2[y][x-1] = loc+1;visited[y][x-1] = 1;
		}

	}

	System.out.println(arr2[n-1][m-1]);
}

}