import java.util.*;
public class Main {
public static final int FLOOR = 0;
public static final int WALL = 1;
public static final int START = 2;
public static final int GOAL = 3;
public static int shortestRoute(int[][] map) {
int startX = -1;
int startY = -1;
int goalX = -1;
int goalY = -1;
int width = map.length;
int height = map[0].length;
int[][] trip = new int[width][height];
// Find start and goal
for (int x=0; x < width; x++) {
for (int y=0; y < height; y++) {
map[x][y] = 0;
if (map[x][y] == START) {
startX = x;
startY = y;
} else if (map[x][y] == GOAL) {
goalX = x;
goalY = y;
}
}
}
ArrayDeque<Point> queue = new ArrayDeque<Point>();
queue.push(new Point(startX, startY));
map[startX][startY] = WALL;
while (queue.size() > 0) {
Point point = queue.pollLast();
int x = point.x;
int y = point.y;
// Go through all four directions
for (int i=0; i < 4; i++) {
int dx = x;
int dy = y;
switch (i) {
case 0:
dy++;
break;
case 1:
dx++;
break;
case 2:
dy--;
break;
case 3:
dx--;
break;
}
if (dx < 0 || dx > width-1 || dy < 0 || dy > height-1) {
continue;
}
if (map[dx][dy] == WALL) {
continue;
}
queue.push(new Point(dx, dy));
map[dx][dy] = WALL;
trip[dx][dy] = trip[x][y]+1;
}
}
if (map[goalX][goalY] == GOAL) {
return -1;
} else {
return trip[goalX][goalY];
}
}
public static void main(String[] args) {
int[][] map = {{1,1,1,1,1,1,1,1},
{1,0,3,1,0,0,0,1},
{1,0,1,1,0,1,0,1},
{1,0,0,0,0,2,0,1},
{1,1,1,1,1,1,1,1}};
System.out.println(shortestRoute(map));
}
}
