我正在解決一些 leetcode 問題并遇到了這個問題：
我得到一個二維陣列，例如：
given[][] = { {1, 6, 2},
{1, 6, 4},
{1, 9, 2} }
陣列中的每個單元格代表我必須從該單元格進行的移動次數。每次我停在一個單元格上時，我只能向上移動或只向左移動。我想找到從陣列右下角到左上角單元格所需的最小移動次數。
例如，在給定的陣列中，我應該回傳 2，從given[2][2]到given[0][2]到，given[0][0]因為這是可能的最短路徑。如果沒有可能到達左上角，我應該回傳-1。
我不知道從哪里開始。任何人都可以提供任何指示嗎？我想我可以將其表示為圖形并應用 Djikstra 演算法，但我不知道這是否是一個可行的解決方案。
uj5u.com熱心網友回復：
我假設所有元素都是正數。
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);
}
輸出：
2
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/374289.html