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.

## Advertisement

## Answer

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