56 lines
1.5 KiB
Java
56 lines
1.5 KiB
Java
import java.util.*;
|
|
|
|
class Point{
|
|
int x;
|
|
int y;
|
|
|
|
Point(int x, int y){
|
|
this.x = x;
|
|
this.y = y;
|
|
}
|
|
}
|
|
|
|
public class _2178{
|
|
public static void main(String[] args) {
|
|
Scanner sc = new Scanner(System.in);
|
|
String[] input = sc.nextLine().split(" ");
|
|
int N = Integer.parseInt(input[0]);
|
|
int M = Integer.parseInt(input[1]);
|
|
int[][] Meero = new int[N+1][M+1];
|
|
int[][] visited = new int[N+1][M+1];
|
|
Queue<Point> queue = new LinkedList<>();
|
|
|
|
for(int i=1; i<=N; i++){
|
|
String[] line = sc.nextLine().split("");
|
|
for(int j=1; j<=M; j++){
|
|
Meero[i][j] = Integer.parseInt(line[j-1]);
|
|
}
|
|
}
|
|
|
|
queue.add(new Point(1,1));
|
|
visited[1][1] = 1;
|
|
int[] dx = {1,-1,0,0};
|
|
int[] dy = {0,0,1,-1};
|
|
|
|
while(queue.size()!=0){
|
|
Point curretPoint = queue.remove();
|
|
int cx = curretPoint.x;
|
|
int cy = curretPoint.y;
|
|
if(cx == M && cy == N){
|
|
System.out.println(visited[cy][cx]);
|
|
break;
|
|
}
|
|
for(int i=0; i<4; i++){
|
|
int nx = cx + dx[i];
|
|
int ny = cy + dy[i];
|
|
if(0<nx && nx<=M && 0<ny && ny<=N && Meero[ny][nx]==1 && visited[ny][nx]==0){
|
|
visited[ny][nx] = visited[cy][cx] + 1;
|
|
queue.add(new Point(nx, ny));
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
sc.close();
|
|
}
|
|
} |