# Untitled

unknown
plain_text
15 days ago
3.2 kB
2
Indexable
Never
```import java.io.*;
import java.util.*;

class Queue {
public static int MAX = 10000000;
private int[] A;
private int front, rear;

Queue() {
A = new int[MAX];
front = 0;
rear = -1;
}

boolean isFull() {
if (rear - front == MAX - 1) {
return true;
}
return false;
}

boolean isEmpty() {
if (front > rear) {
return true;
}
return false;
}

void enqueue(int a) {
if (!isFull()) {
rear++;
A[rear] = a;
}
}

int dequeue() {
if(!isEmpty()) {
front++;
return A[front-1];
}
return -1;
}

int peek() {
if(!isEmpty()) {
return A[front];
}
return -1;
}

void reset() {
front = 0;
rear = -1;
}
}

public class Solution {
public static int N, M, res, startx, starty, endx, endy;
public static int[][] map, visited;
public static Queue queue = new Queue();
public static int[] dx = {-1, 0, 1, 0};
public static int[] dy = {0, 1, 0, -1};

public static boolean bfs(int h) {
queue.enqueue(startx);
queue.enqueue(starty);
visited[startx][starty] = 1;

while(!queue.isEmpty()) {
int newx = queue.dequeue();
int newy = queue.dequeue();

if (newx == endx && newy == endy) {
return true;
}

for (int k = 0; k < 4; k++) {
int nexty = newy + dy[k];

for (int i = 0; i <= h; i++) {
int nextx = newx + dx[k]*i;

if (nextx >= 0 && nextx < N && nexty >= 0 && nexty < M && visited[nextx][nexty] == 0
&& map[nextx][nexty] != 0) {
queue.enqueue(nextx);
queue.enqueue(nexty);
visited[nextx][nexty] = 1;
}
}
}
}
return false;
}

public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
res = -1;
map = new int[N][M];
startx = N-1;
starty = 0;

for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
map[i][j] = sc.nextInt();
if (map[i][j] == 3) {
endx = i;
endy = j;
}
}
}

for (int h = 0; h < N; h++) {
queue.reset();
visited = new int[N][M];
if (bfs(h)) {
res = h;
break;
}
}

System.out.println(res);
sc.close();
}
}```