一、问题说明

矩阵拓扑：

1 2 3 
4 5 6 
7 8 9 
最小权重：21

最小权重路径：
[0, 0] [0, 1] [0, 2] [1, 2] [2, 2] 

二、代码实现

package org.example;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class BackTrace {private int min = Integer.MAX_VALUE;private int[][] list = new int[3][3];private List<int[]> minPath = new ArrayList<>();private void search(int n, int row, int column, int curr, List<int[]> path) {if (row == n-1 && column == n-1) {curr += list[row][column];int[] temp = {row, column};path.add(temp);if (curr < min) {min = curr;minPath = new ArrayList<>(path);}return;}path.add(new int[]{row, column});// right column+1if (column+1 < n) {search(n, row, column+1, curr+list[row][column], path);}// down row+1if (row+1 < n) {search(n, row+1, column, curr+list[row][column], path);}path.remove(path.size()-1);}public static void main(String[] args) {BackTrace backTrace = new BackTrace();int i = 1;for (int j = 0; j < 3; j++) {for (int k = 0; k < 3; k++) {backTrace.list[j][k] = i;i++;}}for (int j = 0; j < 3; j++) {for (int k = 0; k < 3; k++) {System.out.print(backTrace.list[j][k] + " ");}System.out.println();}List<int[]> path = new ArrayList<>();backTrace.search(3, 0, 0, 0, path);System.out.println(backTrace.min);for (int i1 = 0; i1 < backTrace.minPath.size(); i1++) {System.out.print(Arrays.toString(backTrace.minPath.get(i1)) + " ");}}
}