public int shortestDistance(int[][] maze, int[] start, int[] destination) {
if (maze == null || maze.length == 0 || maze[0].length == 0) {
int m = maze.length, n = maze[0].length;
int[][] distance = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(distance[i], Integer.MAX_VALUE);
distance[start[0]][start[1]] = 0;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
getDistanceByDFS(start, destination, distance, maze, directions);
return distance[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : distance[destination[0]][destination[1]];
public void getDistanceByDFS(int[] start, int[] destination, int[][] distance, int[][] maze, int[][] directions) {
int curRow = start[0], curCol = start[1];
if (curRow == destination[0] && curCol == destination[1]) {
for (int[] direction : directions) {
int nextRow = curRow + direction[0];
int nextCol = curCol + direction[1];
int dist = distance[curRow][curCol] + 1;
while (isValid(nextRow, nextCol, maze)) {
if (dist < distance[nextRow][nextCol]) {
distance[nextRow][nextCol] = dist;
getDistanceByDFS(new int[] {nextRow, nextCol}, destination, distance, maze, directions);
public boolean isValid(int row, int col, int[][] maze) {
return row >= 0 && row < maze.length && col >= 0 && col < maze[0].length && maze[row][col] == 0;