Solution.java

public class Solution {

    public static int[][] mainMap;

    public static int yTarget;
    public static int xTarget;
    public static int minDist;

    // Depth First Search : Traverse through the matrix
    public static void traverse(boolean[][] visited, int y, int x, int numberOfJumps, boolean broken) {
        if (x < 0 || y < 0 || x > xTarget || y > yTarget || visited[y][x]) {

        } else {
            
            if (x == xTarget && y == yTarget) {
                if (numberOfJumps < minDist) {
                    minDist = numberOfJumps;
                }
            } else {
                visited[y][x] = true;
            }

            boolean[][] currentVisited = new boolean[yTarget+1][xTarget+1];
            for(int i=0; i<yTarget+1; i++)
                for(int j=0; j<xTarget+1; j++)
                    currentVisited[i][j]=visited[i][j];
            
            if (y < yTarget) {
                if (mainMap[y+1][x] == 1 && !broken) {
                    broken = true;
                    traverse(currentVisited, y+1, x, numberOfJumps+1, broken);
                } else if (mainMap[y+1][x] == 0) {
                    traverse(currentVisited, y+1, x, numberOfJumps+1, broken);
                }
            }
            if (y > 0 && mainMap[y-1][x] == 0) {
                if (mainMap[y-1][x] == 1 && !broken) {
                    broken = true;
                    traverse(currentVisited, y-1, x, numberOfJumps+1, broken);
                } else if (mainMap[y-1][x] == 0) {
                    traverse(currentVisited, y-1, x, numberOfJumps+1, broken);
                }
            }
            if (x < xTarget && mainMap[y][x+1] == 0) {
                if (mainMap[y][x+1] == 1 && !broken) {
                    broken = true;
                    traverse(currentVisited, y, x+1, numberOfJumps+1, broken);
                } else if (mainMap[y][x+1] == 0) {
                    traverse(currentVisited, y, x+1, numberOfJumps+1, broken);
                }
            }
            if (x > 0 && mainMap[y][x-1] == 0) {
                if (mainMap[y][x-1] == 1 && !broken) {
                    broken = true;
                    traverse(currentVisited, y, x-1, numberOfJumps+1, broken);
                } else if (mainMap[y][x-1] == 0) {
                    traverse(currentVisited, y, x-1, numberOfJumps+1, broken);
                }
            }
        }
    }
    
    public static int solution(int[][] map) {
        boolean[][] visited = new boolean[map.length][map[0].length];
        mainMap = map;
        yTarget = map.length - 1;
        xTarget = map[0].length - 1;
        minDist = (yTarget+1)*(xTarget+1);
        traverse(visited, 0, 0, 1, false);
        return minDist;
    }

    public static void main(String[] args) {
        int[][] input = {{0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0}};
        // int[][] input = {{0, 1, 1}, {0, 0, 0}};
        System.out.println(solution(input));
    }
}