I'm working through some leetcode problems and came across this one:

I'm given a 2-D array, for example:

given[][] = { {1, 6, 2},
              {1, 6, 4},
              {1, 9, 2} }

Each cell in the array represents the number of moves I must make from that cell. I can move only up or only left each time I stop on a cell. I want to find the minimum number of moves necessary to go from the bottom right of the array to the top left cell.

For example, in the given array, I should return 2, going from given[2][2] to given[0][2] to given[0][0] as this is the shortest possible path. If there is no possible way to get to the top left, I should return -1.

I'm not sure where to even begin. Can anyone offer any pointers? I was thinking I could represent this as a graph and apply Djikstra's Algorithm, but I don't know if this is a viable solution.

CodePudding user response：

I assume all the elements are positive numbers.

static int minMoves(int[][] given, int x, int y, int count) {
    if (x < 0 || y < 0)
        return Integer.MAX_VALUE;
    if (x == 0 && y == 0)
        return count;
    int step = given[x][y];
    return Math.min(minMoves(given, x - step, y, count   1),
        minMoves(given, x, y - step, count   1));
}

static int minMoves(int[][] given) {
    int count = minMoves(given, given.length - 1, given[0].length - 1, 0);
    return count == Integer.MAX_VALUE ? -1 : count;
}

public static void main(String[] args) {
    int[][] given = {{1, 6, 2}, {1, 6, 4}, {1, 9, 2}};
    int result = minMoves(given);
    System.out.println(result);
}

output:

2