如何遍历所有可能的解决方案路径并选择最佳路径
How to traverse through all possible paths to a solution and pick the optimum path
我不擅长以编程方式实现启发式搜索算法/Dijkstra 算法/提到的 A* 搜索算法。但是，在解决我的 post () 之一中提到的问题时，我发现我解决问题的方法存在缺陷。问题陈述如下。
问题陈述
有一个NxN矩阵，分为N * N个单元格。每个单元格都有一个预定义的值。这将作为输入给出。迭代必须发生 K 次，这也在测试输入中给出。我们必须确保在每次迭代时选择 rows/columns 的 optimum/min 值。最终输出是每次迭代结束时保存的最优值的累加和。
步骤 1. 对单个行和列求和，求行和列的总和的最小值，（可以是行也可以是列，只需要最小的行或列即可）
第2步，将上面找到的总和单独存储
步骤 3. 增加最小值的元素。求和行或列。通过 1
从 1 到第 K 个值重复步骤 1、2、3
在每次迭代中添加总和（在步骤 2 中指定）
输出是第K次迭代得到的总和。
示例数据
2, 4 //input data N,K
[1, 3] //matrix' first row
[2, 4] //matrix' second row
输出数据
22
我的代码
void matrixManipulation() throws IOException {
int N = Reader.nextInt();
int[][] matrix = new int[N][N];
int K = Reader.nextInt();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
matrix[i][j] = Reader.nextInt();
}
}
int[] row = new int[N];
int[] row_clone = new int[N];
int[] col = new int[N];
int[] col_clone = new int[N];
int test =0;
for (int kk = 0; kk < K; kk++) {
row = calculateSum.calculateRowSum(matrix, N);
row_clone = row.clone();
col= calculateSum.calculateColSum(matrix, N);
col_clone = col.clone();
Arrays.sort(col);
Arrays.sort(row);
int pick = 0;
boolean rowflag = false;
int rowNumber = 0;
int colNumber = 0;
if (row[0] < col[0]) {
pick = row[0];// value
rowflag = true;
for (int i = 0; i < N; i++) {
if (pick == row_clone[i])
rowNumber = i;
}
} else if (row[0] > col[0]) {
pick = col[0];// value
rowflag = false;
for (int i = 0; i < N; i++) {
if (pick == col_clone[i])
colNumber = i;
}
}
> else if(row[0] == col[0]){
> pick = col[0];
> rowflag = false;
> for (int i = 0; i < N; i++) {
> if (pick == col_clone[i])
> colNumber = i;
> }
}
test= test + pick;
if (rowflag) {
matrix = rowUpdate(matrix, N, rowNumber);
} else {
matrix = columnUpdate(matrix, N, colNumber);
}
System.out.println(test);
}
}
我的代码有问题
此解决方案适用于一些低阶矩阵和简单场景，但是，当我尝试涉及 100x100 大小矩阵的测试用例时，许多测试用例都失败了。最初，我认为这是数组大小增加时内存 issue/stack 溢出，但现在我发现这是代码中的一个缺陷，我无法预测最终会引导我到达的正确路径我想实现的最佳解决方案。
我在我的代码中发现的缺陷是，在一种情况下，行和列的最佳值相等。我可以自由选择行或列，但是，这里的问题是，如果我先选择行，它可能会将行的值更新为某个非最佳值，我相信只有我事先知道所有最佳路径会帮助我得到正确答案。
在这方面的任何帮助将不胜感激。
此问题引用了此处提出的问题。
只有在使用高阶矩阵时，我才会在应用上述方法时得到以下输出差异。
编辑：
Output Expected Output
1 5499 1 5499
2 30050 2 30050
3 50778 3 50708
4 36589 4 36509
5 19259 5 19259
6 21367 6 21367
案例 3（我的输出是 50778，预期是 50708）
下面的案例 2 示例数据（我的输出是 30066，预期是 30050）
100 57
5 6 5 10 6 3 9 2 4 7 6 6 8 6 5 6 1 6 9 1 6 8 3 7 3 2 4 8 7 8 3 6 3 9 4 2 1 8 5 5 1 5 8 6 6 10 5 3 4 7 3 3 10 10 3 1 7 3 8 4 4 9 3 7 6 7 9 3 2 2 2 4 8 9 8 1 10 6 6 10 7 5 5 7 9 8 3 2 3 3 9 6 3 7 5 5 10 3 3 3
7 6 2 3 8 8 3 10 1 8 4 7 5 2 9 5 3 5 4 6 4 10 1 6 1 5 1 6 4 9 6 4 10 1 2 4 8 10 5 9 1 9 1 9 3 10 9 9 6 5 6 5 9 4 1 4 9 8 6 9 1 3 1 4 9 2 3 4 1 6 4 1 1 8 2 5 10 1 1 10 7 8 7 3 9 3 10 3 10 5 8 3 7 9 10 5 7 3 2 3
4 5 4 6 9 6 6 3 6 3 2 4 9 3 3 6 10 6 3 6 7 7 9 8 9 3 6 6 3 4 9 6 2 5 9 9 9 1 5 1 7 4 9 7 10 3 1 8 1 9 9 3 1 4 6 1 8 10 3 1 10 5 9 4 3 6 8 8 1 3 5 9 1 9 9 4 3 5 1 7 1 1 9 2 1 9 7 4 7 8 7 3 3 9 6 9 10 7 10 5
2 9 4 3 4 5 6 8 5 5 8 2 3 2 1 2 5 1 10 6 5 6 6 8 4 8 3 6 6 3 3 1 6 3 3 7 6 4 2 7 1 5 9 8 9 5 8 8 10 8 8 8 10 7 3 1 8 6 7 2 2 5 9 8 10 10 10 3 2 6 8 9 6 10 6 10 5 10 9 7 6 4 5 6 4 8 7 10 3 5 9 1 5 7 5 5 9 9 3 10
10 2 1 8 2 2 7 3 6 8 10 8 4 1 3 9 3 8 4 8 7 5 4 1 5 3 2 1 6 3 8 8 8 9 10 4 8 10 9 1 4 1 5 5 9 2 1 2 4 1 3 7 5 8 7 2 5 1 2 2 5 4 4 2 3 2 9 6 5 3 6 5 2 6 9 3 4 7 9 4 1 8 5 10 3 1 3 6 8 8 6 3 1 4 8 6 2 6 6 1
2 7 3 9 10 8 5 8 1 1 7 6 2 3 4 1 2 3 9 2 2 1 2 2 7 10 8 4 4 9 9 6 3 9 9 4 8 2 5 3 1 2 9 1 2 3 1 9 4 7 7 1 10 8 9 9 6 7 5 2 8 3 1 1 7 4 8 7 10 9 10 7 9 4 10 8 4 10 1 1 10 2 2 9 8 8 1 3 4 2 10 2 2 3 3 7 4 6 6 1
4 1 5 9 2 7 3 9 5 8 8 5 1 7 1 10 1 3 1 4 2 3 7 1 4 3 5 5 8 5 6 10 2 10 6 2 1 10 9 2 3 8 2 6 9 3 2 1 4 9 6 6 7 1 6 1 8 6 1 4 10 10 2 3 1 9 9 2 9 1 5 8 8 1 10 10 8 1 1 7 4 7 7 2 9 8 1 5 10 10 3 5 6 10 4 2 10 6 10 9
5 3 3 7 7 4 10 4 6 4 3 4 5 6 4 1 4 3 3 2 1 5 1 1 10 3 3 8 6 9 9 6 10 3 3 1 6 9 2 8 7 1 7 10 8 4 7 5 8 4 9 10 9 8 4 4 3 2 4 3 10 10 5 7 8 1 9 3 8 1 4 9 3 5 9 1 3 4 8 10 5 2 4 5 2 7 5 5 1 2 9 6 1 2 3 10 4 5 9 9
10 10 2 7 10 9 2 1 3 4 6 10 5 1 10 7 3 5 7 9 8 9 4 7 6 4 8 3 9 10 9 1 5 5 7 7 10 8 6 3 9 4 2 6 6 7 5 2 1 4 6 9 3 5 9 5 8 6 8 2 1 3 6 2 2 4 5 1 1 10 2 1 6 2 10 8 3 3 6 1 2 1 4 10 4 6 6 9 7 6 7 8 2 7 9 3 9 10 1 5
9 3 4 4 8 4 9 1 1 9 7 4 8 1 5 3 2 3 5 4 7 2 6 6 9 5 8 5 2 4 1 3 2 5 7 6 2 8 3 6 10 10 3 3 8 2 4 10 3 4 10 8 2 3 5 2 10 9 3 4 3 4 6 7 6 8 7 3 7 3 1 4 2 4 5 2 5 5 10 4 1 1 7 1 9 6 5 5 7 2 8 2 6 2 10 10 4 3 1 10
6 2 4 7 3 7 4 4 8 1 6 1 9 5 3 2 6 1 7 1 4 8 4 4 1 1 4 8 1 4 5 2 4 2 6 7 3 2 9 5 5 3 3 1 7 10 4 9 10 4 2 4 6 3 4 1 1 7 3 1 2 10 7 9 3 2 8 7 1 1 5 8 7 9 7 8 9 5 1 6 7 6 6 2 10 4 4 8 10 7 4 4 10 5 6 1 9 4 5 4
5 1 2 3 4 6 10 8 1 3 2 3 7 10 4 2 5 10 5 10 8 4 8 5 2 3 2 7 10 6 8 2 1 6 9 1 3 6 8 9 8 7 3 7 2 5 2 7 3 2 5 3 1 5 1 5 4 2 4 4 6 7 5 1 9 6 1 6 5 6 6 7 4 3 1 9 8 6 2 1 8 5 7 7 7 9 1 1 10 6 4 4 1 8 3 10 6 7 1 5
4 6 7 3 8 1 1 7 8 10 8 4 9 7 7 3 4 2 10 6 5 6 2 9 8 2 9 7 10 6 3 3 1 1 3 3 2 7 4 8 4 5 3 7 9 1 5 7 2 4 9 5 4 4 1 10 3 7 6 9 3 8 10 5 5 5 1 4 2 10 4 9 5 5 1 7 6 3 3 8 6 6 10 6 5 10 9 4 10 10 10 6 6 7 8 3 4 1 10 9
8 2 8 2 3 2 4 1 8 3 5 9 8 6 6 9 1 4 2 1 7 3 5 9 1 8 2 5 1 1 5 7 5 9 9 1 10 3 6 1 2 10 9 3 1 10 2 4 10 6 8 6 9 10 7 5 10 10 9 6 8 2 5 9 3 2 4 9 8 8 9 3 5 10 8 1 3 3 2 7 2 1 5 10 10 3 10 7 4 8 9 4 6 2 5 4 8 9 10 4
9 7 3 9 9 9 2 3 6 6 2 1 9 10 6 4 2 10 8 7 8 9 3 10 9 5 6 2 5 1 10 1 4 4 10 6 6 8 4 6 8 9 3 1 4 4 10 1 3 7 6 7 5 6 7 9 4 6 6 6 8 2 8 9 7 4 6 9 7 10 8 6 9 3 6 6 5 3 3 8 10 3 9 1 3 8 5 2 8 10 8 7 5 6 10 7 6 5 9 9
7 9 6 1 8 4 8 8 9 2 10 7 1 4 6 4 5 5 5 10 3 10 8 3 7 1 4 9 10 6 10 3 9 2 8 3 8 4 6 4 8 3 4 4 10 1 1 5 10 2 8 8 4 2 4 6 5 5 9 1 5 10 1 3 5 5 10 9 7 1 1 5 4 6 4 3 10 5 3 2 3 2 10 1 3 7 10 6 8 2 8 8 8 7 6 10 9 4 5 6
2 4 9 1 1 7 2 3 6 10 5 3 9 4 9 1 1 2 8 7 3 2 8 6 4 2 10 7 7 5 1 5 8 9 7 5 8 2 10 8 8 8 9 10 7 1 2 2 5 4 9 10 1 4 4 9 8 6 8 7 2 3 4 1 8 8 1 3 4 7 4 10 2 10 7 7 6 8 7 9 4 6 10 8 2 6 2 7 5 5 4 7 9 10 2 7 3 3 3 4
10 7 9 5 7 10 3 7 6 10 7 4 3 3 1 1 1 7 1 2 8 9 5 2 7 6 6 5 5 5 10 3 4 9 6 9 2 3 3 5 1 9 2 2 5 9 5 7 3 6 4 7 5 1 10 2 3 5 6 6 5 4 1 4 9 3 3 7 8 2 1 7 1 6 1 10 4 6 1 6 10 6 7 2 9 7 4 2 8 2 2 7 6 3 3 3 5 2 1 10
3 9 4 1 8 1 1 3 5 6 7 3 4 8 1 7 6 2 2 3 7 1 7 1 7 8 10 8 7 6 10 7 9 10 9 9 9 2 10 3 8 5 10 7 9 10 7 8 9 4 3 5 7 10 10 6 4 10 1 9 8 1 6 5 9 8 10 4 9 10 7 9 8 8 1 7 4 7 9 3 4 5 7 1 3 6 5 1 9 3 3 10 4 2 5 10 7 9 5 2
1 6 8 8 4 7 6 5 6 6 3 6 10 4 6 5 7 9 1 1 2 4 3 6 10 1 10 8 7 1 1 7 9 1 4 7 7 4 6 6 6 7 10 3 5 5 8 3 4 10 7 1 1 1 6 4 5 1 9 6 7 2 8 3 8 3 1 2 7 7 4 6 8 9 7 4 7 3 6 1 5 4 10 5 6 3 4 10 8 6 8 8 5 3 10 1 4 1 8 5
4 3 2 2 10 4 7 10 6 8 9 2 2 7 7 10 3 6 9 6 3 1 5 10 8 4 10 2 9 3 1 5 9 4 7 8 5 1 1 1 5 2 9 4 7 4 4 6 6 1 8 10 6 5 10 9 9 10 5 5 4 3 9 2 9 3 3 4 4 8 2 1 9 8 10 1 2 7 4 4 9 2 9 2 4 9 8 6 6 8 7 3 10 6 7 1 2 7 5 6
4 3 10 5 4 6 6 1 3 7 5 5 2 4 9 6 3 7 4 7 1 10 7 10 5 6 9 2 3 6 6 3 6 8 5 7 1 5 5 6 2 7 8 4 5 4 2 7 1 5 6 4 6 7 8 3 3 7 8 10 1 4 9 10 2 1 9 5 8 8 8 4 1 9 4 4 10 4 4 4 3 10 9 7 9 4 3 7 10 7 7 9 4 10 6 5 6 6 9 7
3 8 7 1 7 2 9 5 5 6 2 10 10 8 3 10 3 1 4 6 1 8 6 10 9 7 5 3 9 10 3 5 5 1 5 10 4 4 6 3 7 8 9 4 1 10 10 5 6 10 10 1 9 9 1 9 9 3 9 10 9 3 5 1 9 9 4 8 4 3 4 6 10 10 7 6 8 9 2 9 6 7 5 3 8 7 4 7 8 2 5 4 6 8 7 1 8 9 2 6
8 7 7 2 6 7 1 2 4 10 3 1 2 5 10 8 6 9 9 6 4 10 5 4 3 2 10 9 2 9 5 5 4 5 9 8 10 7 8 3 8 4 7 1 10 2 2 7 1 7 8 9 7 9 2 6 3 5 5 3 6 1 2 10 4 2 5 5 4 8 4 1 4 3 10 1 1 8 8 4 5 2 3 4 6 3 7 9 4 5 7 8 4 5 3 5 10 7 8 8
1 6 9 9 8 6 4 9 8 2 2 1 10 6 7 4 8 8 2 2 1 4 3 3 5 7 6 6 5 9 9 10 1 5 7 3 6 4 1 9 10 4 10 8 8 5 7 10 7 8 7 10 6 8 6 6 10 3 9 9 5 3 3 9 5 1 5 8 5 5 7 1 2 7 5 9 9 6 9 3 10 1 1 2 5 9 7 5 3 6 8 4 1 3 3 10 1 10 6 5
8 7 10 8 1 1 5 10 2 9 6 4 8 7 8 3 6 3 2 5 8 2 2 6 6 9 9 4 8 1 8 9 2 4 3 4 2 8 6 1 5 10 4 10 3 3 5 2 1 9 3 5 3 6 7 10 1 5 10 3 3 6 4 9 1 6 4 4 8 7 1 7 9 9 6 3 4 6 5 4 4 4 1 3 9 5 2 2 9 8 7 6 5 10 3 6 4 8 7 8
1 1 9 9 9 9 8 4 7 1 4 5 9 9 9 1 5 7 3 4 6 6 7 4 5 4 9 2 7 10 7 9 8 2 7 8 9 10 8 10 5 8 5 9 10 3 2 5 5 9 4 8 3 8 3 10 10 9 7 5 6 10 10 10 4 3 1 5 9 1 9 3 6 3 1 4 7 10 10 10 8 7 10 6 1 2 6 7 2 10 4 2 5 3 9 6 9 6 5 2
10 2 9 4 9 4 9 1 6 1 5 3 5 10 6 7 1 4 1 7 9 1 1 4 7 7 8 10 7 3 5 3 5 5 4 8 7 1 7 4 8 7 10 3 7 3 2 6 8 9 4 9 2 6 6 4 3 7 6 5 3 2 1 4 6 1 6 3 6 4 1 4 4 5 8 1 7 2 3 6 10 1 4 3 4 3 5 1 6 1 3 9 5 8 2 3 3 3 8 2
8 3 5 7 6 6 6 4 8 9 8 10 7 4 5 10 4 9 10 2 2 5 6 4 10 6 6 2 4 8 9 2 10 3 5 5 7 1 7 6 8 4 2 3 5 5 3 5 7 2 4 3 8 5 9 1 4 8 5 5 7 4 2 4 10 1 2 7 10 3 7 10 6 9 8 3 2 7 2 2 5 3 5 8 10 7 3 5 3 9 3 10 9 1 2 8 4 2 1 10
7 3 5 8 8 6 5 5 9 8 4 2 2 8 2 6 7 8 8 6 6 10 8 6 3 4 5 1 3 10 5 8 2 4 6 5 7 9 7 10 9 4 1 3 2 1 3 10 9 3 8 7 9 1 2 1 10 8 3 1 3 7 2 10 10 8 9 4 4 5 1 2 6 6 9 2 8 7 5 7 9 7 6 5 7 1 4 6 10 4 7 3 8 5 10 8 4 8 8 7
1 2 1 2 6 8 4 2 1 6 7 5 7 9 7 8 9 9 1 10 6 9 2 4 10 1 9 8 7 3 7 3 3 6 4 4 5 6 10 4 9 6 9 9 4 1 3 8 4 2 3 5 4 7 7 1 10 2 1 4 5 2 4 10 4 10 1 6 2 6 3 9 8 4 4 8 3 1 7 10 9 5 5 2 1 6 3 4 4 8 7 9 9 6 6 10 8 7 8 10
4 1 9 4 5 6 6 10 9 6 7 5 8 1 3 9 5 10 6 7 7 10 8 8 9 4 3 4 3 6 1 9 5 10 5 8 4 10 7 4 2 6 6 10 6 4 4 3 5 8 6 4 2 4 8 3 7 4 2 9 1 1 6 2 6 1 5 6 7 10 6 2 6 6 3 4 10 2 1 1 8 5 6 7 5 3 8 10 2 10 6 2 6 9 1 8 5 7 1 1
3 3 2 1 7 2 4 1 3 2 2 8 4 7 1 2 2 10 4 9 8 9 10 8 2 9 9 6 10 2 5 2 8 8 10 7 6 10 1 7 3 8 4 7 9 7 1 7 2 4 6 5 4 1 2 10 8 4 9 7 10 5 8 2 8 7 6 2 9 8 5 6 3 5 10 10 9 6 6 3 1 7 9 10 10 1 3 8 3 3 9 1 2 3 8 6 5 7 10 8
9 8 6 2 10 4 4 4 10 9 2 5 1 1 9 7 3 8 9 8 6 10 5 9 5 4 1 6 2 9 9 4 9 6 10 5 6 3 3 2 2 2 4 4 2 5 5 6 10 7 10 5 1 5 10 9 9 2 6 10 2 5 7 5 8 3 4 3 4 8 4 5 7 7 10 4 7 7 2 6 8 9 4 5 6 9 3 9 3 8 1 10 4 3 5 7 4 5 1 10
3 1 2 9 7 5 1 1 8 4 7 6 7 10 1 6 7 3 4 2 7 10 8 4 7 8 10 5 1 9 4 3 10 9 9 9 1 5 7 8 10 6 5 2 10 9 4 2 6 4 5 9 10 8 10 2 1 4 5 10 7 2 3 9 9 9 2 9 4 3 2 10 6 1 9 8 5 1 5 2 7 1 3 1 9 4 7 1 4 6 8 8 10 9 1 8 7 1 5 2
7 7 7 10 2 10 3 7 1 4 7 1 7 6 6 6 10 4 5 2 1 9 3 1 10 2 1 7 7 1 10 3 3 1 1 2 3 8 2 8 7 6 3 6 6 10 5 8 6 1 10 7 7 1 10 8 4 4 1 7 3 2 10 8 6 2 1 4 4 5 6 7 4 9 1 5 5 1 1 9 5 5 8 1 3 3 9 8 2 10 8 9 2 9 6 8 3 3 3 3
2 8 4 9 5 7 10 5 9 10 2 7 8 1 2 4 10 2 4 1 8 4 3 2 9 7 8 7 10 8 1 5 9 4 5 10 5 10 2 10 10 2 2 2 1 3 1 3 4 1 6 9 7 4 8 4 10 9 8 3 2 8 1 10 4 8 1 8 6 1 5 8 4 2 2 7 7 2 2 5 4 1 7 1 8 7 10 1 10 1 10 9 9 10 1 7 6 1 6 7
6 2 1 6 5 7 2 9 6 10 6 4 3 7 7 9 9 8 7 1 7 7 8 2 5 7 1 10 7 6 2 1 5 10 10 7 2 8 9 10 9 9 1 1 3 10 2 6 3 8 4 2 9 6 7 5 5 2 7 4 7 9 5 1 7 1 5 3 1 4 5 10 7 6 7 8 6 5 8 2 1 10 8 2 9 4 3 10 10 8 5 8 6 3 2 1 4 4 9 3
3 10 6 5 3 9 10 8 5 1 3 4 9 4 8 10 2 7 6 8 6 1 1 3 3 8 5 7 10 4 7 5 2 2 4 10 5 4 9 6 4 5 9 6 10 7 6 7 6 7 1 3 8 5 1 1 4 2 4 10 1 4 5 10 5 9 2 6 7 2 3 1 3 1 1 9 2 5 1 10 10 2 4 10 3 6 2 6 4 5 9 8 7 9 8 9 8 2 3 9
7 10 4 1 3 6 10 7 1 2 6 8 9 9 4 2 3 6 2 1 4 6 9 1 6 7 6 10 4 6 6 4 7 8 6 7 5 8 6 10 10 7 5 7 10 10 7 1 10 10 4 2 10 9 2 5 3 9 8 2 2 7 9 4 8 4 10 3 8 9 9 1 8 4 9 4 3 7 7 9 1 8 7 8 3 6 6 1 2 1 6 5 9 5 3 1 6 2 6 10
10 5 5 3 9 10 6 5 3 6 5 4 7 9 6 10 7 5 5 2 10 9 6 9 7 9 9 3 5 5 9 3 4 4 7 3 9 8 1 6 3 2 8 5 6 6 8 3 6 8 7 7 4 2 4 6 10 4 6 8 5 4 7 5 1 2 9 9 6 5 10 9 4 10 4 8 6 4 9 2 1 5 1 7 3 3 5 1 3 7 8 1 2 10 9 2 4 5 3 2
9 5 1 3 7 10 10 9 9 3 8 3 8 5 4 5 3 3 5 7 9 7 5 8 3 6 5 2 6 3 8 6 8 10 8 2 8 3 2 7 1 8 9 3 4 3 3 4 1 5 2 10 4 7 7 7 3 5 8 3 1 2 8 8 7 5 9 4 6 9 5 3 7 8 1 1 1 5 2 1 10 7 3 8 8 4 3 6 3 6 4 1 8 3 7 4 8 10 10 3
1 10 10 7 3 3 10 3 8 2 5 2 8 4 9 3 8 9 10 5 7 1 6 10 9 2 2 2 10 7 8 2 6 1 8 4 7 3 6 3 7 6 8 5 4 5 5 7 8 9 5 9 8 4 6 9 5 9 8 5 7 7 3 10 1 9 10 3 4 9 10 9 6 4 9 6 6 5 7 4 7 4 6 10 3 9 4 5 7 3 2 9 3 1 1 3 1 10 7 10
6 10 4 9 6 8 3 9 1 6 7 9 1 7 6 5 1 1 3 2 10 7 9 5 8 8 8 8 9 3 3 6 4 8 2 4 3 9 5 1 8 5 9 9 8 2 5 10 10 6 4 4 6 9 9 3 1 5 8 1 7 7 6 4 10 2 3 5 8 8 8 2 10 1 5 2 4 2 2 9 4 7 9 4 3 1 3 9 7 6 6 7 8 2 2 5 5 6 4 4
5 10 2 9 9 7 7 6 3 4 2 6 7 3 6 3 4 3 1 4 9 5 4 6 9 8 8 5 4 4 1 9 6 10 8 8 2 2 8 7 5 3 2 6 3 6 2 5 2 9 5 8 2 9 10 5 6 1 2 5 8 6 2 10 8 2 9 5 10 3 10 6 3 3 1 10 8 9 5 2 1 9 2 3 6 5 5 8 10 9 2 10 7 2 8 5 7 4 7 9
8 9 4 1 6 1 3 9 10 8 7 1 5 8 9 2 7 6 3 6 3 5 8 7 6 1 3 6 7 2 6 8 7 6 8 8 4 4 8 9 5 3 9 1 5 4 6 5 9 1 8 2 7 1 9 6 5 7 9 7 1 1 6 3 1 6 2 6 10 2 4 7 2 3 9 8 7 9 2 6 7 6 8 7 9 4 4 8 8 4 4 2 10 7 8 5 1 7 1 1
5 3 4 7 4 4 4 9 10 4 8 5 2 6 4 5 2 9 5 10 5 8 10 2 7 7 2 2 4 10 2 8 6 4 7 1 2 3 2 1 6 6 10 4 3 9 5 1 4 3 6 7 1 10 10 10 3 4 9 4 2 4 2 8 10 5 8 7 5 2 9 2 2 1 8 4 8 2 9 8 5 5 6 5 2 7 4 2 2 6 9 6 5 4 3 5 6 4 6 8
2 7 5 10 10 8 10 6 4 10 10 2 8 9 8 5 1 4 2 2 4 10 4 8 7 8 10 8 7 4 5 7 10 3 5 5 6 4 10 4 10 4 6 7 3 6 6 7 3 10 2 3 6 1 5 1 2 2 6 4 4 1 7 6 6 7 8 1 8 3 9 4 7 10 7 1 6 7 5 6 4 7 3 3 10 3 4 7 2 1 6 2 5 9 7 7 3 7 1 8
5 2 10 8 2 4 1 5 6 2 7 6 2 2 10 2 9 8 1 5 2 5 8 1 9 10 3 3 2 3 2 5 4 6 4 1 5 6 5 5 8 9 9 8 3 2 5 3 10 9 5 3 4 9 8 3 10 5 5 6 2 1 1 8 9 1 6 9 4 10 1 1 10 8 9 8 2 5 2 4 10 6 3 10 10 6 6 7 2 7 7 9 10 7 7 7 10 9 10 10
8 7 4 10 6 3 7 3 7 6 4 9 10 4 7 4 8 6 2 9 5 4 6 2 3 5 1 6 10 2 5 7 7 8 2 1 3 3 9 6 3 2 10 3 5 4 7 1 2 5 9 5 9 7 10 8 10 6 9 8 3 6 8 10 2 9 1 4 5 7 1 10 7 2 1 3 6 9 2 1 6 1 9 8 9 3 4 3 2 1 2 6 9 3 1 10 3 7 9 3
1 9 8 10 4 5 1 9 6 4 1 5 7 8 4 1 7 5 8 1 5 7 6 2 2 5 3 2 2 8 4 9 1 9 2 8 6 3 6 8 2 2 2 8 8 6 9 7 5 4 4 10 5 8 7 2 7 10 2 4 7 10 4 5 3 1 8 9 5 9 4 10 7 6 3 5 7 3 8 9 5 10 1 5 2 4 6 5 7 10 8 1 5 10 10 5 3 7 3 3
8 9 6 6 9 10 5 8 1 1 2 9 9 9 2 6 1 3 2 9 4 4 1 9 5 2 8 1 5 10 3 8 3 7 10 5 4 10 8 5 10 4 4 9 6 7 1 10 10 2 6 4 5 1 1 10 10 8 2 5 1 1 3 7 5 6 2 8 4 9 8 3 10 6 2 5 3 3 8 10 2 7 9 5 9 7 9 2 1 3 10 7 1 9 7 10 1 1 2 6
6 10 1 5 10 1 4 5 10 5 4 2 2 8 4 2 4 7 7 9 1 5 7 5 2 1 3 6 6 5 5 5 10 7 7 6 10 9 10 3 9 3 2 10 8 9 9 3 5 9 8 4 3 9 3 1 4 1 9 4 3 3 3 2 1 3 1 4 1 5 3 4 5 5 10 2 7 10 9 2 5 6 1 9 4 6 4 10 1 9 4 8 6 1 10 6 7 4 5 5
1 6 6 9 5 3 3 6 5 9 1 2 1 4 9 4 7 9 2 7 10 9 7 6 4 2 5 3 9 6 7 2 5 3 1 3 5 4 5 3 3 7 10 7 3 7 7 5 7 7 6 3 3 9 1 10 7 3 10 7 4 4 3 6 8 1 8 4 7 9 8 10 3 2 6 2 6 8 5 1 7 2 8 2 2 5 5 5 7 6 8 3 10 1 8 9 7 5 8 3
8 2 5 2 9 6 8 2 10 8 2 10 3 9 9 7 6 1 1 3 7 3 2 10 5 1 5 7 4 1 3 6 9 6 9 3 8 3 6 10 2 4 9 9 10 7 5 8 7 2 1 5 9 2 1 2 2 8 5 10 8 6 8 7 7 9 6 6 1 6 3 5 9 8 1 1 5 10 8 9 9 4 2 5 4 7 7 3 3 8 6 3 4 9 10 8 4 7 8 10
10 10 3 5 7 4 6 7 10 2 6 3 8 9 8 3 10 5 9 2 6 9 4 3 6 3 10 1 7 2 9 4 7 4 8 2 7 8 4 8 8 2 4 5 4 10 7 9 1 2 3 9 2 4 6 2 10 7 3 9 6 4 3 6 6 4 6 9 8 2 2 2 7 2 6 6 6 4 9 8 2 1 7 5 5 10 10 9 10 6 10 3 7 7 8 3 6 4 6 8
8 7 3 4 1 6 9 7 6 10 10 10 10 2 9 1 10 10 9 9 2 6 9 4 5 6 3 6 1 5 1 3 2 5 2 6 9 4 5 4 6 9 10 5 5 2 9 1 8 10 8 6 7 6 7 10 1 10 9 5 9 6 8 7 10 7 10 6 10 1 1 4 3 4 2 5 2 10 10 7 9 7 7 3 6 8 4 1 1 5 3 10 7 3 8 5 3 5 5 1
3 2 3 8 5 8 2 10 6 9 8 9 7 7 8 4 10 2 5 4 4 5 8 4 8 5 1 6 3 9 8 6 6 1 1 1 8 9 5 7 8 8 8 3 9 5 10 7 5 2 7 4 4 4 8 8 10 9 6 1 8 5 10 9 1 6 4 4 2 3 6 9 5 4 8 6 4 1 5 2 7 5 8 2 1 1 10 1 5 7 9 9 5 1 5 8 10 10 5 1
10 6 8 10 9 4 8 3 4 10 8 6 4 6 7 6 10 7 10 4 7 6 7 9 3 1 9 2 5 4 2 5 7 1 3 5 5 2 1 7 8 8 1 7 2 9 5 6 3 1 2 10 1 1 7 3 5 8 9 6 7 9 9 8 2 7 3 10 1 8 5 3 7 3 4 6 4 1 2 8 3 9 2 9 1 8 7 6 1 6 4 2 7 7 9 5 10 1 2 2
1 1 4 4 8 1 1 8 5 8 5 4 4 10 1 1 4 10 10 5 8 6 3 8 8 4 3 9 1 9 2 6 9 6 4 1 1 1 5 10 5 3 1 10 4 8 7 3 9 2 1 3 4 10 5 6 4 9 5 2 1 4 4 6 8 6 10 10 6 8 4 4 3 1 4 2 5 9 1 2 4 4 2 6 10 1 7 4 9 4 8 3 5 4 1 1 5 4 10 1
7 1 5 2 10 5 8 2 1 9 7 4 6 1 6 9 1 8 7 3 9 3 5 5 3 2 7 8 5 7 3 2 1 9 3 10 8 9 1 3 1 1 8 1 9 1 8 2 3 1 5 7 8 6 8 6 10 4 8 3 2 3 8 3 7 9 1 6 7 2 7 3 1 10 8 3 7 6 6 8 3 10 5 4 8 1 2 1 2 8 6 9 3 10 7 10 1 4 9 3
8 9 10 1 7 5 9 10 5 4 6 4 7 1 1 5 1 8 6 7 10 10 4 9 1 5 3 10 2 5 9 1 6 1 4 7 2 4 1 9 1 9 5 9 6 10 3 6 2 4 9 1 6 5 10 8 5 10 7 10 5 8 1 9 3 10 5 6 1 8 6 1 7 8 10 7 1 8 8 2 5 4 9 1 10 6 4 6 6 3 4 7 10 6 7 9 3 7 3 1
4 4 8 7 10 5 2 5 7 1 10 7 10 7 9 3 3 10 2 7 5 4 4 2 1 8 9 4 5 9 6 10 7 5 5 6 2 2 1 8 2 3 4 2 10 6 3 2 3 3 5 7 7 4 4 4 10 2 10 9 4 5 8 8 8 8 3 1 3 9 10 10 7 6 7 10 4 10 1 9 8 9 8 2 10 6 5 4 8 5 10 10 8 3 1 9 10 10 3 2
4 8 6 5 4 1 5 4 5 8 9 10 7 10 2 5 5 7 9 4 6 5 8 3 2 8 4 2 5 4 2 2 9 4 6 8 9 3 6 10 8 6 3 7 9 5 1 6 5 4 7 5 5 8 3 1 3 1 1 9 5 3 1 3 8 10 10 4 5 5 4 6 1 2 6 7 8 9 10 2 6 2 9 7 1 4 10 8 7 6 6 4 1 10 8 6 8 2 7 8
7 10 5 9 10 5 6 4 6 9 1 10 4 7 6 1 5 6 3 6 1 7 7 5 6 3 8 6 5 5 2 6 4 6 4 7 1 5 1 10 8 4 4 4 9 5 4 1 6 7 7 3 8 1 5 10 10 2 10 2 10 10 10 6 8 3 3 8 7 7 4 10 1 2 5 9 5 1 7 10 4 1 9 10 7 2 7 3 2 9 2 7 1 3 1 9 2 4 7 6
5 8 9 8 2 9 2 10 4 2 5 5 1 9 7 2 7 3 1 5 9 10 6 10 5 10 2 8 7 1 7 2 1 4 1 9 10 3 4 5 1 2 6 4 9 3 5 3 7 4 10 5 9 3 3 7 8 2 3 3 6 3 9 4 4 7 7 1 4 4 10 2 3 6 5 4 7 9 1 4 7 7 8 5 7 7 10 10 7 10 6 8 9 6 5 5 2 6 5 4
3 6 4 10 5 4 9 8 10 6 7 5 9 6 10 3 5 5 6 7 6 10 1 9 5 3 5 3 9 2 10 7 2 8 1 5 9 9 5 10 10 7 5 9 5 6 9 9 6 2 9 5 7 8 10 3 6 7 5 2 8 5 1 9 6 8 2 6 7 1 7 9 7 6 7 5 5 5 2 8 9 9 5 3 5 1 5 10 8 5 4 5 2 10 3 8 8 4 4 5
3 4 9 6 3 8 9 1 3 4 9 10 8 1 4 1 5 6 10 8 9 2 4 1 9 4 1 6 8 8 9 10 2 5 2 9 4 5 2 7 1 1 6 10 6 8 10 6 4 10 10 10 6 3 6 4 4 8 6 2 7 1 9 2 6 7 8 3 10 6 4 9 5 6 3 6 1 5 9 7 4 9 6 1 8 8 2 5 1 5 5 10 7 5 5 1 9 3 1 10
7 6 8 10 3 6 5 10 3 2 7 5 8 9 10 6 7 2 9 7 6 2 7 1 6 5 1 8 7 8 2 10 5 5 9 8 1 7 5 2 8 7 9 6 5 4 5 6 10 2 4 9 10 4 9 6 7 2 2 5 1 5 9 3 9 4 5 4 9 5 3 6 9 1 3 5 1 1 9 1 4 7 6 8 5 10 5 5 1 1 2 10 2 4 2 4 10 1 9 4
6 4 8 5 6 6 1 6 7 2 3 4 4 2 8 6 5 10 4 10 2 2 10 3 6 5 10 3 10 7 3 5 10 4 4 3 10 7 6 4 4 3 6 8 5 10 3 2 1 1 7 6 1 6 10 5 2 9 7 3 2 7 1 10 6 2 10 10 3 10 5 3 7 1 8 9 7 5 1 4 5 3 6 4 1 6 10 10 10 10 9 3 6 6 4 4 10 1 4 5
6 8 8 1 8 4 6 1 4 5 3 7 10 5 3 4 10 10 10 5 3 7 5 10 3 4 1 4 5 6 5 4 6 7 7 6 6 2 8 10 1 7 9 1 1 4 10 4 7 1 5 10 1 3 5 1 5 5 2 3 5 1 2 8 1 8 3 8 5 8 5 9 5 10 4 1 7 10 5 7 5 9 5 5 1 8 7 5 6 2 1 6 4 2 7 7 1 8 1 4
6 3 3 3 1 10 10 5 7 1 2 2 3 3 6 9 4 4 2 4 7 4 6 9 8 7 5 2 4 5 9 1 9 7 2 5 10 10 4 10 7 6 5 9 2 7 1 2 2 10 9 10 2 10 3 6 5 10 3 5 2 1 3 10 7 5 10 5 5 4 8 9 10 7 4 2 9 10 1 7 5 5 1 3 7 3 2 9 6 4 1 7 4 7 5 10 4 7 10 10
5 3 2 8 10 3 3 1 4 1 4 10 3 10 6 10 8 9 5 7 9 4 5 4 3 3 3 10 3 7 9 10 7 3 9 3 4 6 6 10 10 10 5 6 7 3 4 1 1 1 7 2 3 5 4 7 4 8 4 8 2 1 6 1 5 6 8 5 8 4 2 10 10 8 4 5 4 5 6 3 8 7 1 1 1 3 9 10 1 10 5 1 7 5 6 1 9 10 10 2
7 3 10 2 10 4 9 4 5 3 5 10 10 8 1 4 5 2 1 4 1 9 9 7 1 5 6 7 4 9 4 9 6 4 5 9 2 5 8 8 2 10 9 4 10 4 10 6 3 5 1 4 2 7 6 3 4 8 1 9 10 1 4 7 3 5 4 8 2 1 8 8 5 3 10 8 4 9 7 1 3 6 5 1 2 4 7 1 6 8 5 5 8 7 5 6 9 7 7 3
7 5 7 10 5 2 8 8 6 2 10 7 9 2 6 10 7 8 3 3 10 4 5 9 8 10 9 10 6 5 6 1 10 3 4 6 5 6 8 3 7 7 9 7 7 10 4 3 7 2 3 3 3 5 10 3 3 10 1 4 7 1 8 2 9 8 7 9 4 10 1 7 1 9 7 6 3 9 3 10 3 3 10 4 4 8 6 10 4 9 7 6 2 3 7 6 3 5 4 9
6 6 3 7 5 4 2 1 5 10 6 9 9 3 3 5 6 9 10 6 5 1 6 1 3 1 5 7 8 3 1 3 4 10 5 2 1 8 6 2 3 6 1 7 5 7 4 5 4 3 9 1 10 4 9 4 4 7 8 6 1 9 6 1 1 7 10 3 8 6 5 10 10 10 9 10 3 5 8 7 3 2 9 4 9 6 3 2 5 3 10 4 9 8 3 9 3 6 9 8
2 8 1 3 5 10 1 6 7 5 6 10 4 6 1 8 5 1 7 3 4 1 6 4 10 6 3 6 9 8 2 5 4 7 7 1 7 4 8 1 4 7 7 2 10 5 7 3 9 2 3 4 3 4 2 2 5 6 8 10 2 1 6 1 10 2 9 10 5 10 4 8 8 10 2 5 3 4 8 6 7 9 1 5 8 6 5 9 7 5 2 1 6 2 6 9 10 2 5 7
3 2 4 9 8 4 3 4 2 7 3 4 7 8 7 1 9 8 5 5 7 10 8 4 4 8 5 1 7 10 2 8 2 6 10 1 7 2 6 1 10 6 9 6 5 1 4 5 5 6 3 3 1 9 7 5 8 9 8 4 1 4 8 4 8 10 7 9 2 3 9 4 7 7 8 10 4 1 3 9 9 9 2 5 4 3 4 6 5 6 8 4 7 3 5 2 9 1 5 10
5 9 4 1 1 5 6 9 5 5 3 6 9 10 6 6 6 10 9 5 4 7 2 10 7 2 6 9 10 6 1 4 1 9 1 9 1 6 9 5 5 1 5 5 1 8 7 10 5 3 9 6 3 3 4 6 8 7 5 9 3 3 4 7 6 8 6 9 6 7 7 2 8 4 3 7 9 8 2 6 10 10 10 7 7 7 1 8 3 7 2 2 7 10 7 8 9 6 2 9
5 3 10 1 8 2 4 10 1 9 10 2 4 10 5 5 1 6 4 5 3 4 5 3 1 2 5 6 7 1 6 1 3 6 8 3 4 4 10 1 6 4 8 2 1 4 7 1 9 9 2 7 3 4 6 10 8 6 1 2 6 7 6 8 5 1 7 8 8 8 5 7 6 8 4 4 5 8 8 3 5 8 2 1 6 3 7 4 6 3 6 7 4 4 2 5 4 2 9 7
4 6 5 6 2 5 4 4 8 9 3 7 9 8 5 5 9 9 3 3 2 7 6 1 2 7 9 7 1 8 3 8 2 8 10 9 5 2 10 6 3 8 1 7 8 4 8 8 7 3 5 3 4 7 3 5 3 5 3 5 1 5 2 3 9 5 6 9 1 7 6 2 6 10 8 10 4 4 3 5 6 3 10 2 10 1 3 8 10 8 8 5 1 9 4 10 1 2 3 2
7 3 1 1 1 4 8 8 9 5 8 10 2 10 1 5 6 1 1 5 9 2 8 8 2 6 4 1 1 1 10 9 4 9 7 5 6 4 6 7 2 10 6 1 3 6 2 2 8 3 6 2 7 10 2 1 8 3 6 3 8 2 4 1 3 9 8 8 2 1 9 10 8 9 3 10 7 6 1 2 6 5 1 2 7 8 6 10 10 1 8 9 1 9 3 3 7 9 2 5
7 3 3 7 10 5 6 7 4 10 8 8 3 7 5 9 4 5 4 7 8 4 5 10 4 9 5 10 3 5 9 3 9 8 1 4 6 6 9 8 7 4 5 8 5 7 6 5 2 8 5 9 1 9 8 6 8 9 8 1 4 8 3 2 4 1 7 3 3 3 8 1 4 10 4 6 7 7 10 1 1 4 8 10 2 4 9 6 5 9 8 4 2 6 3 5 6 2 9 3
9 8 4 6 1 2 5 7 2 3 3 10 10 10 9 5 7 6 10 3 6 7 2 9 3 10 10 5 3 1 5 8 1 7 9 8 3 2 1 3 4 7 6 7 10 7 7 1 10 7 1 10 4 5 5 9 10 9 10 6 3 7 8 1 3 5 2 10 5 2 8 7 9 10 10 2 2 8 9 7 1 1 9 10 3 10 6 2 9 1 4 8 8 8 5 5 1 1 10 9
6 2 3 1 8 8 6 1 8 1 4 6 10 7 5 5 5 2 8 10 3 3 2 7 5 5 10 8 9 1 4 1 2 5 7 8 10 8 5 3 9 5 3 6 10 5 10 1 6 3 5 1 10 3 6 8 3 3 4 1 8 3 6 5 4 7 10 1 10 5 10 3 10 1 8 5 3 3 8 10 8 1 5 3 9 8 2 6 8 3 1 6 6 3 3 6 5 8 3 4
7 3 1 10 10 9 5 7 4 6 8 2 6 1 1 9 6 1 7 7 2 2 9 9 1 3 3 6 8 2 3 2 8 7 7 7 5 7 6 4 10 4 7 5 1 5 2 1 5 2 1 5 10 10 7 3 7 8 10 5 7 1 1 2 2 3 1 7 2 4 4 4 4 9 4 1 6 6 9 6 6 7 8 7 2 5 7 2 6 4 3 10 9 9 1 1 8 8 7 2
7 3 6 6 3 9 4 5 7 9 6 3 10 1 7 1 7 4 6 4 2 1 7 3 3 1 7 10 6 7 5 2 7 9 8 8 2 6 6 6 7 1 10 10 6 6 9 5 5 2 2 3 8 5 1 9 7 1 4 7 1 3 4 3 5 10 1 5 10 7 7 6 8 2 9 1 10 1 1 8 1 3 1 4 7 5 7 6 8 7 5 6 1 5 3 10 8 4 1 7
4 5 6 4 5 6 6 1 2 9 7 1 2 5 6 9 2 3 2 5 1 1 1 9 3 1 6 5 3 1 3 10 6 1 2 8 1 3 6 9 3 7 1 5 2 1 5 5 2 4 10 7 6 1 3 3 7 3 10 6 9 9 4 7 2 10 8 4 3 3 8 1 2 1 4 9 8 5 1 7 3 5 6 10 4 8 3 7 9 7 4 4 9 10 6 3 4 2 8 10
7 7 10 10 4 4 2 5 8 6 6 2 2 3 2 3 6 1 4 7 5 1 9 6 3 3 4 10 5 5 1 5 8 2 10 9 3 7 2 2 3 1 5 7 5 2 6 10 4 1 10 10 5 4 8 6 7 7 7 6 3 4 9 4 10 10 10 7 3 1 1 10 3 6 10 5 8 5 4 6 8 3 2 6 5 2 9 3 7 3 2 4 1 7 9 10 4 5 2 6
2 1 6 10 2 3 9 5 4 5 4 8 4 6 3 4 5 2 5 3 3 4 3 4 5 9 7 2 6 3 3 9 9 1 7 7 3 7 7 10 8 8 2 5 10 4 2 3 1 8 5 1 6 3 8 5 8 8 6 5 4 1 2 6 6 7 10 10 4 2 3 9 8 5 10 6 2 3 1 6 4 2 7 4 5 7 2 3 4 5 8 6 8 6 4 1 6 3 3 6
8 8 6 6 6 7 1 2 6 4 4 1 5 5 5 1 9 3 9 2 6 6 5 4 2 3 1 7 5 10 3 9 3 8 8 7 5 4 5 8 7 3 10 1 5 10 7 2 2 9 7 9 2 6 6 2 3 6 7 1 1 2 5 3 4 10 10 4 8 5 9 7 5 8 6 1 7 9 3 10 4 5 6 5 3 9 1 3 9 2 7 2 7 8 9 2 4 3 4 1
4 7 4 3 3 4 7 4 8 6 5 6 4 10 5 10 7 10 8 9 10 6 7 7 9 3 7 4 7 6 3 4 8 6 9 4 7 8 8 4 10 7 10 6 2 4 7 7 3 7 3 3 6 6 8 6 5 10 1 1 8 1 2 4 2 6 4 1 6 4 6 6 5 4 5 6 7 1 5 3 6 8 8 1 10 7 6 7 10 5 2 4 7 4 9 3 3 8 3 6
6 7 2 7 9 9 8 6 1 5 10 9 7 6 6 9 8 3 6 3 3 9 7 1 10 5 2 8 4 5 9 10 8 7 5 7 9 9 1 1 10 5 9 4 6 9 6 1 8 10 2 1 8 3 8 10 8 9 3 3 10 3 2 4 8 3 3 3 8 1 8 7 2 6 3 1 7 9 6 1 10 1 1 7 10 9 7 1 1 10 6 1 3 3 6 8 1 4 5 10
3 5 9 8 7 8 7 5 10 5 9 4 9 8 8 1 4 5 3 4 6 5 10 4 1 10 5 1 8 3 5 5 2 5 10 8 4 5 6 10 10 6 3 6 1 5 9 8 2 10 3 1 2 7 7 8 3 4 9 9 10 5 2 7 1 7 9 3 1 3 3 3 1 3 1 10 1 9 1 7 1 3 2 6 5 3 9 1 2 6 2 8 1 4 6 9 4 3 6 9
4 5 3 3 10 7 1 2 4 4 9 2 10 3 7 3 2 8 5 8 7 7 6 1 3 5 8 1 1 2 9 4 8 10 1 6 1 2 5 6 5 5 7 6 5 2 1 7 9 10 8 8 3 9 1 6 6 3 8 3 7 2 10 7 4 7 8 10 1 9 9 7 9 10 4 5 8 8 2 7 10 6 6 2 1 1 10 9 6 1 6 1 10 3 2 7 9 4 7 3
7 1 4 8 1 6 8 10 9 10 8 2 4 1 4 7 1 5 4 7 8 8 8 5 4 5 8 8 1 5 6 2 1 3 9 4 7 1 2 1 8 8 10 2 5 6 4 1 3 5 10 1 10 6 9 3 7 5 9 3 1 8 1 1 2 7 1 2 1 9 4 8 5 1 6 9 3 8 6 1 5 9 6 9 9 10 1 1 3 7 1 3 6 9 3 4 8 4 10 10
1 7 7 9 3 4 3 3 10 7 1 10 2 10 5 1 4 9 4 8 5 4 10 10 2 1 5 6 7 3 7 9 8 3 10 5 6 5 1 3 5 10 7 2 6 4 3 3 5 2 7 7 2 10 4 9 4 1 7 8 3 6 4 2 8 8 6 2 2 10 7 10 5 7 3 6 5 1 4 7 9 9 2 2 8 5 8 7 9 4 8 3 8 4 10 10 4 7 6 6
6 4 10 9 5 3 7 10 4 8 9 3 1 8 4 3 8 10 6 3 3 2 2 9 5 6 3 10 8 3 10 3 7 9 3 4 2 3 4 8 5 6 7 7 8 7 6 10 6 4 9 10 1 2 1 8 5 3 4 3 9 1 1 5 2 7 9 2 8 9 7 2 5 1 7 1 7 1 2 2 4 8 8 7 10 2 7 8 2 6 7 6 4 6 7 4 9 10 8 6
8 6 7 8 10 9 3 3 10 10 4 9 2 10 3 8 2 7 10 4 4 6 2 5 10 3 10 5 3 7 9 10 6 3 5 8 3 2 9 8 5 9 8 2 9 6 4 5 6 2 10 5 1 7 5 2 4 1 8 1 9 4 1 8 8 3 9 6 3 3 6 6 7 2 6 10 4 1 9 10 2 10 5 4 4 2 3 8 8 2 3 4 7 4 3 5 6 4 10 9
7 10 9 6 9 2 9 1 4 5 8 10 1 5 6 6 2 4 1 1 7 9 7 7 8 10 3 2 5 2 3 9 7 3 8 8 7 7 3 7 1 5 6 8 6 8 8 1 5 3 3 5 6 4 5 4 9 1 9 9 1 4 8 7 4 4 8 6 2 5 9 10 7 3 7 7 4 9 8 10 2 9 1 5 7 7 10 4 5 2 1 6 2 3 5 9 3 8 2 4
这是我找到的算法。它是 O(n^2) 所以它是最佳的。为什么？您必须阅读 n^2 个单元格，以便 OPT 至少为 O(n^2)。
计算所有行和所有列的总和。像这样将它们存储在 class 中：
public class Sum implements Comparable {
public long currentSum;
public boolean isRow;
public int index;
public Sum(long sum, boolean row, int i) {
currentSum = sum;
isRow = row;
index = i;
}
public Sum(Sum s) {
currentSum = s.currentSum;
isRow = s.isRow;
index = s.index;
}
@Override
public int compareTo(Object o) {
Sum s = (Sum)o;
return Long.compare(this.currentSum, s.currentSum);
}
}
算法为：
1. If there is a column or a row which has the smallest sum (i.e. it's the only lowest sum) - choose it.
2. If there are more then one smallest sums:
a)if there are no rows with smallest sum - pick column
b)if there are no cols with smallest sum - pic row
c)Try both out otherwise
将 Sum 存储在 heap 中 - 例如java.util.PriorityQueue。最好自己写堆。它也可以是您要排序的列表，但效率较低。在这里你必须做一些研究，当一半元素递增和一个强烈扩大时，哪种数据结构在求助时最有效。
我已经使用 ArrayList 实现了工作解决方案。随意使用它，但您必须稍微更改代码以提高效率。
//Creates list of all available sums. Sorts them and passes to calculate
public static int solution(int[][] a, int K, int n) {
List<Sum> sums = new ArrayList<>();
for (int i = 0; i < n; i++) {
int rowSum = 0;
int colSum = 0;
for (int j = 0; j < n; j++) {
rowSum += a[i][j];
colSum += a[j][i];
}
sums.add(new Sum(rowSum, true, i));
sums.add(new Sum(colSum, false, i));
}
Collections.sort(sums);
return calculate(sums, K, n, 0);
}
public static int calculate(List<Sum> sums, int K, int n, int res) {
//if (K < 50) System.out.println(K);
int result = res;
for (int i = 0; i < K; i++) {
Collections.sort(sums);
Sum chosenSum;
if (sums.get(0).currentSum == sums.get(1).currentSum && K > 1) {
long low = sums.get(0).currentSum;
int colCount = 0;
int rowCount = 0;
Sum rows = null;
Sum cols = null;
for (Sum s : sums) {
if (s.currentSum == low) {
if (s.isRow) {
rowCount++;
if (rows == null) {
rows = s;
}
} else {
colCount++;
if (cols == null) {
cols = s;
}
}
}
}
if (colCount == 0) {
chosenSum = rows;
} else if (rowCount == 0) {
chosenSum = cols;
} else {
chosenSum = (calculate(copySums(sums), K - i, n, new Sum(rows)) < calculate(copySums(sums), K - i, n, new Sum(cols)) ? rows : cols);
}
} else {
chosenSum = sums.get(0);
}
result += chosenSum.currentSum;
chosenSum.currentSum += n;
for (Sum s : sums) {
if (chosenSum.isRow ^ s.isRow) {
s.currentSum++;
}
}
Collections.sort(sums);
}
return result;
}
public static int calculate(List<Sum> sums, int K, int n, Sum chosenSum) {
for (Sum s : sums) {
if (chosenSum.isRow ^ s.isRow) {
s.currentSum++;
}
if (s.isRow == chosenSum.isRow && s.index == chosenSum.index) {
s.currentSum += n;
}
}
Collections.sort(sums);
return calculate(copySums(sums), K, n, (int) chosenSum.currentSum);
}
public static List<Sum> copySums(List<Sum> sums) {
ArrayList<Sum> result = new ArrayList<>();
for (Sum s : sums) {
result.add(new Sum(s));
}
return result;
}
此代码 returns 30050 以防 100 57。 100 93 测试用例仍然 50778。
我是 Java 的新手。因此，我正在使用这种天真的方法来查找您的问题的结果。
我正在计算行总和和列总和并找到最小值并相应地将其递增 +1。
当我遇到行和列的相同值时，即当我尝试保留上一次迭代的行和列值并从那里获取下一个最小值并递增它时。
此外，我不仅处理了 NxN 矩阵，还处理了 MxN 矩阵。
下面是我解决这个问题的方法：
try {
for (k = 0; k < 4; k++) {
int rowSum[] = new int[arr.length];
int columnSum[] = new int[arr[0].length];
// Gets the sum for rows
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < ((arr[0].length)); j++) {
rowSum[i] = rowSum[i] + arr[i][j];
}
}
System.out.println("Row sum is: " + Arrays.toString(rowSum));
// Gets the sum for columns
for (int j = 0; j < arr[0].length; j++) {
for (int i = 0; i < (arr.length); i++) {
columnSum[j] = columnSum[j] + arr[i][j];
}
}
System.out.println("Column sum is: " + Arrays.toString(columnSum));
// to find the smallest
int minRowSumValue = rowSum[0];
for (int i = 0; i < rowSum.length; i++) {
if (rowSum[i] < minRowSumValue) {
minRowSumValue = rowSum[i];
}
}
System.out.println("Min row sum value is: " + minRowSumValue);
int minColSumValue = columnSum[0];
for (int i = 0; i < columnSum.length; i++) {
if (columnSum[i] < minColSumValue) {
minColSumValue = columnSum[i];
}
}
System.out.println("Min column sum value is: " + minColSumValue);
if (minRowSumValue < minColSumValue) {
int a = getArrayIndex(rowSum, minRowSumValue);
for (int i = a; i < arr.length; i++) {
for (int j = 0; j < ((arr[0].length)); j++) {
arr[i][j] = arr[i][j] + 1;
}
oldMinSumColValue = minColSumValue;
oldMinSumRowValue = 0;
finalSum += minRowSumValue;
break;
}
} else if (minColSumValue < minRowSumValue) {
int a = getArrayIndex(columnSum, minColSumValue);
for (int j = a; j < arr[0].length; j++) {
for (int i = 0; i < (arr.length); i++) {
arr[i][j] = arr[i][j] + 1;
}
oldMinSumRowValue = minRowSumValue;
oldMinSumColValue = 0;
finalSum += minColSumValue;
break;
}
} else if(minRowSumValue == minColSumValue) {
if (oldMinSumRowValue != 0) {
int a = getArrayIndex(rowSum, oldMinSumRowValue);
for (int i = a; i < arr.length; i++) {
for (int j = 0; j < ((arr[0].length)); j++) {
arr[i][j] = arr[i][j] + 1;
}
finalSum += minRowSumValue;
break;
}
} else {
int a = getArrayIndex(columnSum, oldMinSumColValue);
for (int j = a; j < arr[0].length; j++) {
for (int i = 0; i < (arr.length); i++) {
arr[i][j] = arr[i][j] + 1;
}
finalSum += minColSumValue;
break;
}
}
}
System.out.println("\nArray is: " + Arrays.deepToString(arr));
}
System.out.println("\n\nFinal Array after "+k+" steps is: " + Arrays.deepToString(arr));
System.out.println("\nFinal sum value is: "+finalSum);
} catch (Exception e) {
// TODO: handle exception
System.out.println("Exception is: " + e);
}
您可以通过使用更好的方法轻松提高效率。
下面是我的代码。当它遇到不明确的情况时（当在行和列中都可以找到最小值时），它会尝试两种情况并输出最小值。
对于每次迭代，它都会对两个 n 值列表进行排序。所以复杂度是 O(C*k*n log n)，其中 C 是不同路径的数量。我相信这非常接近最佳（就暴力的复杂性而言），因为在每次迭代之后，恰好 n+1 值会发生变化，因此我们至少需要触及它们中的每一个（当然，除非，一些更多的算法洞察力让我们只接触其中的几个）。根据 k 和 n 的值，这可能不够好，也可能不够好。对于案例 2，它运行的时间略多于 1 秒。
import java.util.Scanner;
import java.io.File;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;
/**
* 11 Aug 2016
* To answer the following question:
*
*/
class MinRowCol {
public static boolean DEBUG = false;
public static boolean USE_QUICK_ALGO = false;
public static boolean PREFER_ROW = true;
public static boolean USE_SUM_COUNT = false;
public static void inc(HashMap<Integer, Integer> sumCount, int key){
int oldVal = sumCount.getOrDefault(key, 0);
sumCount.put(key, oldVal+1);
}
public static void dec(HashMap<Integer, Integer> sumCount, int key){
int oldVal = sumCount.getOrDefault(key, 0);
sumCount.put(key, oldVal-1);
}
/**
* The class to store a sum
*/
private static final class Sum implements Comparable<Sum>{
public int sum;
public boolean isRow;
/** Count the number of each sum appearing as row sum (used in quick algo) */
public static HashMap<Integer, Integer> rowSumCount = new HashMap<Integer, Integer>();
/** Count the number of each sum appearing as col sum (used in quick algo) */
public static HashMap<Integer, Integer> colSumCount = new HashMap<Integer, Integer>();
public Sum(int sum, boolean isRow){
this.sum = sum;
this.isRow = isRow;
}
/**
* Returns how many times this sum appears in the matrix
* This function is used in quick algo
*/
public int getSumCount(){
int sumCount = 0;
if(this.isRow){
sumCount = rowSumCount.get(this.sum);
} else {
sumCount = colSumCount.get(this.sum);
}
return sumCount;
}
/**
* Update this sum with the diff
* This will properly update the sum count (this feature is for quick algo)
*/
public void update(int diff){
HashMap<Integer, Integer> sumCount;
if(this.isRow){
sumCount = rowSumCount;
} else {
sumCount = colSumCount;
}
dec(sumCount, this.sum);
inc(sumCount, this.sum+diff);
this.sum += diff;
}
/**
* Compare based on sum value
* In quick algo, if the value is the same, the one with higher multiplicity
* (i.e., appearing multiple times) has priority (i.e., smaller than the other)
*/
public int compareTo(Sum s){
if(this.sum < s.sum){
return -1;
} else if(this.sum > s.sum){
return 1;
} else {
if(USE_QUICK_ALGO){
if(USE_SUM_COUNT){
int result = -Integer.compare(this.getSumCount(), s.getSumCount());
if(result != 0){
return result;
}
}
if(PREFER_ROW){
return Boolean.compare(this.isRow, s.isRow);
} else {
return -Boolean.compare(this.isRow, s.isRow);
}
} else {
return 0;
}
}
}
public String toString(){
if(USE_QUICK_ALGO){
return String.format("%d %d %s", this.sum, this.getSumCount(), this.isRow ? "row" : "col");
} else {
return String.format("%d %s", this.sum, this.isRow ? "row" : "col");
}
}
}
public static void main(String[] args) throws Exception{
String inputFile = args[0];
if(args.length > 1){
for(int i=1; i<args.length; i++){
if(args[i].equals("-v")){
DEBUG = true;
} else if(args[i].equals("-quick")){
USE_QUICK_ALGO = true;
} else if(args[i].equals("-prefer_row")){
PREFER_ROW = true;
} else if(args[i].equals("-prefer_col")){
PREFER_ROW = false;
} else if(args[i].equals("-use_sum_count")){
USE_SUM_COUNT = true;
}
}
}
Scanner scanner = new Scanner(new File(inputFile));
String line = scanner.nextLine();
String[] tokens = line.split(" ");
int n = Integer.parseInt(tokens[0]);
int k = Integer.parseInt(tokens[1]);
int[][] matrix = new int[n][n];
Sum[] rowSums = new Sum[n];
Sum[] colSums = new Sum[n];
for(int i=0; i<n; i++){
rowSums[i] = new Sum(0, true);
colSums[i] = new Sum(0, false);
}
HashMap<Integer, Integer> rowSumCount = Sum.rowSumCount;
HashMap<Integer, Integer> colSumCount = Sum.colSumCount;
// Initialize the row sum and col sum
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
matrix[i][j] = scanner.nextInt();
rowSums[i].sum += matrix[i][j];
colSums[j].sum += matrix[i][j];
}
}
// Initialize the sum count (NOT USED)
for(int i=0; i<n; i++){
Sum rowSum = rowSums[i];
int val = rowSumCount.getOrDefault(rowSum.sum, 0);
rowSumCount.put(rowSum.sum, val+1);
Sum colSum = colSums[i];
val = colSumCount.getOrDefault(colSum.sum, 0);
colSumCount.put(colSum.sum, val+1);
}
int totSum = minSum(rowSums, colSums, 0, k, new String[k], 0);
System.out.println(totSum);
}
/**
* Returns the minimum sum after running the procedure for (maxIter-iter) iterations
* The arguments `selected` and `totSoFar` are for recording the path and the minimum sum, respectively
*/
public static int minSum(Sum[] rowSums, Sum[] colSums, int iter, int maxIter, String[] selected, int totSoFar){
int totSum = 0;
int n = rowSums.length;
// Consider the minimum in the row and the minimum in the column
// We don't need to consider multiple minimum values in a row/column
// since once a minimum value in a row gets picked, the next iteration
// will surely choose the minimum in the row, since the minimum in
// the column is no longer a minimum
Sum minRow = null;
Sum minCol = null;
for(int j=0; j<n; j++){
if(minRow == null || rowSums[j].sum < minRow.sum){
minRow = rowSums[j];
}
if(minCol == null || colSums[j].sum < minCol.sum){
minCol = colSums[j];
}
}
// Either try both row and column, or just pick row or pick column
Sum[] minSums;
if(minRow.compareTo(minCol) < 0){
minSums = new Sum[]{minRow};
} else if (minRow.compareTo(minCol) > 0){
minSums = new Sum[]{minCol};
} else {
minSums = new Sum[]{minRow, minCol};
}
int curMinSum = minSums[0].sum; // The minimum row/column sum in this iteration
int subSums = Integer.MAX_VALUE; // To hold the minimum sum after this iteration
for(Sum minSum: minSums){ // Try all (either one or two) choices
// Update the sums
if(minSum.isRow){
for(int j=0; j<n; j++){
colSums[j].update(1);
}
} else {
for(int j=0; j<n; j++){
rowSums[j].update(1);
}
}
selected[iter] = minSum.toString();
minSum.update(n);
if(iter < maxIter - 1){
int nextSubSums = minSum(rowSums, colSums, iter+1, maxIter, selected, totSoFar+curMinSum);
if(nextSubSums < subSums){
subSums = nextSubSums;
}
} else {
subSums = 0;
if(DEBUG){
System.out.print("End ("+(totSoFar+curMinSum)+"): ");
for(int i=0; i<selected.length; i++){
System.out.print(selected[i]+" ");
}
System.out.println();
}
}
// Revert the sum update we have done earlier
minSum.update(-n);
if(minSum.isRow){
for(int j=0; j<n; j++){
colSums[j].update(-1);
}
} else {
for(int j=0; j<n; j++){
rowSums[j].update(-1);
}
}
}
// Return minimum row/col found at this iter + the minimum sum in
// all iterations after this iteration
return curMinSum + subSums;
}
}
如果您提供 -v 参数，它也可以打印它选择的路径：
java MinRowCol MinRowCol.test -v
还有其他选项：
-quick - This will reduce the number of cases explored by using heuristics. The heuristics can be specified with other options
-prefer_col - This will prefer column over row (by default prefer row)
-use_sum_count - This will use the multiplicity of the sum
小测试用例如下：
3 2
1 0 1
0 1 1
0 0 1
它将输出：
End (3): 1 row 2 row
End (3): 1 row 2 col
End (2): 1 col 1 col
2
意味着它找到了三个可能的路径，其中两个的值为 3，一个的得分为 2。所以它选择了值为 2 的那个，你可以看到它做出的选择（总和和 row/col).您可以看到，首先选择列会导致最后的值变小。
案例三（案例二的选项太多，这里就不一一展示了）四个案例的答案是一样的：
End (50778): 455 1 col 480 1 col 486 1 row 494 1 col 498 1 row 500 1 col 502 1 col 506 1 col 509 1 col 510 1 col 512 2 row 512 1 row 513 1 row 514 1 row 515 1 row 519 2 row 519 1 row 520 1 row 524 1 row 525 1 col 526 1 col 527 1 col 529 1 row 530 1 row 531 1 row 533 1 row 534 2 row 534 1 row 535 2 row 535 1 row 538 2 row 538 1 row 539 2 row 539 1 row 541 3 row 541 2 row 541 1 row 542 1 row 543 2 row 543 1 row 544 2 row 544 1 row 545 1 row 548 1 row 549 3 row 549 2 row 549 1 row 550 1 row 553 3 row 553 2 row 553 1 row 554 2 row 554 1 row 556 1 row 557 2 row 557 1 row 558 1 row 559 3 row 559 2 row 559 1 row 561 1 row 563 2 row 563 1 row 564 4 row 564 3 row 564 2 row 564 1 row 565 1 row 567 2 row 567 1 row 569 1 row 570 2 row 570 1 row 571 1 row 572 1 row 573 1 row 574 3 row 574 2 row 574 1 row 575 2 row 575 1 row 576 2 row 576 1 row 577 2 row 577 1 row 578 2 row 578 1 row 579 1 row 582 1 row 583 2 row 583 1 row 584 2 row 584 1 row
End (50778): 455 1 col 480 1 col 486 1 row 494 1 col 498 1 row 500 1 col 502 1 col 506 1 col 509 1 col 510 1 col 512 2 row 512 1 row 513 1 row 514 1 row 515 1 row 519 2 row 519 1 row 520 1 row 524 1 col 525 1 row 526 1 col 527 1 col 529 1 row 530 1 row 531 1 row 533 1 row 534 2 row 534 1 row 535 2 row 535 1 row 538 2 row 538 1 row 539 2 row 539 1 row 541 3 row 541 2 row 541 1 row 542 1 row 543 2 row 543 1 row 544 2 row 544 1 row 545 1 row 548 1 row 549 3 row 549 2 row 549 1 row 550 1 row 553 3 row 553 2 row 553 1 row 554 2 row 554 1 row 556 1 row 557 2 row 557 1 row 558 1 row 559 3 row 559 2 row 559 1 row 561 1 row 563 2 row 563 1 row 564 4 row 564 3 row 564 2 row 564 1 row 565 1 row 567 2 row 567 1 row 569 1 row 570 2 row 570 1 row 571 1 row 572 1 row 573 1 row 574 3 row 574 2 row 574 1 row 575 2 row 575 1 row 576 2 row 576 1 row 577 2 row 577 1 row 578 2 row 578 1 row 579 1 row 582 1 row 583 2 row 583 1 row 584 2 row 584 1 row
End (50778): 455 1 col 480 1 col 486 1 row 494 1 col 498 1 row 500 1 col 502 1 col 506 1 col 509 1 col 510 1 col 512 2 row 512 1 row 513 1 row 514 1 row 515 1 row 519 2 row 519 1 row 520 1 row 524 1 col 525 1 col 526 1 row 527 1 col 529 1 row 530 1 row 531 1 row 533 1 row 534 2 row 534 1 row 535 2 row 535 1 row 538 2 row 538 1 row 539 2 row 539 1 row 541 3 row 541 2 row 541 1 row 542 1 row 543 2 row 543 1 row 544 2 row 544 1 row 545 1 row 548 1 row 549 3 row 549 2 row 549 1 row 550 1 row 553 3 row 553 2 row 553 1 row 554 2 row 554 1 row 556 1 row 557 2 row 557 1 row 558 1 row 559 3 row 559 2 row 559 1 row 561 1 row 563 2 row 563 1 row 564 4 row 564 3 row 564 2 row 564 1 row 565 1 row 567 2 row 567 1 row 569 1 row 570 2 row 570 1 row 571 1 row 572 1 row 573 1 row 574 3 row 574 2 row 574 1 row 575 2 row 575 1 row 576 2 row 576 1 row 577 2 row 577 1 row 578 2 row 578 1 row 579 1 row 582 1 row 583 2 row 583 1 row 584 2 row 584 1 row
End (50778): 455 1 col 480 1 col 486 1 row 494 1 col 498 1 row 500 1 col 502 1 col 506 1 col 509 1 col 510 1 col 512 2 row 512 1 row 513 1 row 514 1 row 515 1 row 519 2 row 519 1 row 520 1 row 524 1 col 525 1 col 526 1 col 527 1 row 529 1 row 530 1 row 531 1 row 533 1 row 534 2 row 534 1 row 535 2 row 535 1 row 538 2 row 538 1 row 539 2 row 539 1 row 541 3 row 541 2 row 541 1 row 542 1 row 543 2 row 543 1 row 544 2 row 544 1 row 545 1 row 548 1 row 549 3 row 549 2 row 549 1 row 550 1 row 553 3 row 553 2 row 553 1 row 554 2 row 554 1 row 556 1 row 557 2 row 557 1 row 558 1 row 559 3 row 559 2 row 559 1 row 561 1 row 563 2 row 563 1 row 564 4 row 564 3 row 564 2 row 564 1 row 565 1 row 567 2 row 567 1 row 569 1 row 570 2 row 570 1 row 571 1 row 572 1 row 573 1 row 574 3 row 574 2 row 574 1 row 575 2 row 575 1 row 576 2 row 576 1 row 577 2 row 577 1 row 578 2 row 578 1 row 579 1 row 582 1 row 583 2 row 583 1 row 584 2 row 584 1 row
50778
对于情况2，结果如下：
没有选项（搜索所有案例）：
30050
使用-quick -prefer_row:
30066
使用-quick -prefer_col:
30050
所以我们确实需要探索多条路径。但我不确定为什么情况 3 的正确答案应该是 50708 而不是 50778。
您实际上不需要保留整个矩阵，只需要按行和按列的总和。
给定一个 NxN 矩阵，令 SumByRow 为长度为 N 的向量，其中包含矩阵每一行的总和，令 SumByCol 与列相同。在您的示例中，这些向量将是：
Matrix = [ [1,3],
[2,4]]
SumByRow = [4,6]
SumByCol = [3,7]
现在，无论最小行[列]的实际索引如何，我们都可以确定一件事：在下一次迭代中，SumByRow[Col] 向量的一个元素将递增 N（因为我们正在添加一个到该行 [列] 的每个元素）并且 SumByCol [行] 将向其每个元素添加 1（因为无论总和是什么，我们将一对一且仅将组成它的元素之一相加）。
所以我们可以摆脱丑陋的大矩阵并使用这两个向量。
上面的推理也提出了一种实现迭代的方法，即：
Step one: find index of minimum element between both vectors
Step two: increase final sum by that element's value, increase that element by N, increase each element of other vector by one
Step three: rinse and repeat until smooth anf fluf- enough iterations have been calculated
最后一个问题，行列求和的最小值相同怎么办？
随机并没有真正的帮助，也不是总是选择一个而不是另一个，因为这些方法可能会让你进入一个次优的车道，然后需要某种形式的前瞻性。
我选择了一个简单的模拟，如果两个选项都无效，下一步会发生什么，以递归但有限的方式，以便尽可能多地尝试和展望未来。
但是可能会有更有效的启发式方法，甚至是完全完整的策略，但 none 现在我想到了。
编辑：
实际上，多亏了 justhalf，我不再确定局部贪婪方法有什么好处，因为最优策略可能从一些不是明确最优的选择开始...
这是我拼凑来演示的代码，它很丑陋，但我希望可以理解，如果您发现错误或需要任何说明，请告诉我
https://ideone.com/EZW3wt
from numpy import matrix
import numpy as np
n = 2
k = 4
A = matrix([[1,3],
[2,4]
])
sc = [0]*n
sr = [0]*n
for i in range(0,n):
sc[i] = sum( A.A[:,i] )
sr[i] = sum( A.A[i,:] )
output=0
def whichmin(c,r, iter):
if(iter < 0):
return 1
r[np.argmin(r)] += n
c[np.argmin(c)] += n
if ( np.amin(c) < np.amin(r) ):
return 1
elif ( np.amin(r) < np.amin(c) ):
return 0
else :
return whichmin(c,r, (iter -1) )
for j in range(0,k):
minc = np.amin(sc)
minr = np.amin(sr)
if (minc < minr):
incrindex = np.argmin(sc)
sc[incrindex]+=n
sr = [x+1 for x in sr]
output += minc
elif (minr < minc):
incrindex = np.argmin(sr)
sr[incrindex]+=n
sc = [x+1 for x in sc]
output += minr
else :
min = whichmin(sc.copy(),sr.copy(), (n - i) )
if (min==1):
incrindex = np.argmin(sc)
sc[incrindex]+=n
sr = [x+1 for x in sr]
output += minc
else:
incrindex = np.argmin(sr)
sr[incrindex]+=n
sc = [x+1 for x in sc]
output += minr
print(output)
print(sc)
print(sr)
我不擅长以编程方式实现启发式搜索算法/Dijkstra 算法/提到的 A* 搜索算法。但是，在解决我的 post (
问题陈述
有一个NxN矩阵，分为N * N个单元格。每个单元格都有一个预定义的值。这将作为输入给出。迭代必须发生 K 次，这也在测试输入中给出。我们必须确保在每次迭代时选择 rows/columns 的 optimum/min 值。最终输出是每次迭代结束时保存的最优值的累加和。
步骤 1. 对单个行和列求和，求行和列的总和的最小值，（可以是行也可以是列，只需要最小的行或列即可）
第2步，将上面找到的总和单独存储
步骤 3. 增加最小值的元素。求和行或列。通过 1
从 1 到第 K 个值重复步骤 1、2、3
在每次迭代中添加总和（在步骤 2 中指定）
输出是第K次迭代得到的总和。
示例数据
2, 4 //input data N,K
[1, 3] //matrix' first row
[2, 4] //matrix' second row
输出数据 22
我的代码
void matrixManipulation() throws IOException {
int N = Reader.nextInt();
int[][] matrix = new int[N][N];
int K = Reader.nextInt();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
matrix[i][j] = Reader.nextInt();
}
}
int[] row = new int[N];
int[] row_clone = new int[N];
int[] col = new int[N];
int[] col_clone = new int[N];
int test =0;
for (int kk = 0; kk < K; kk++) {
row = calculateSum.calculateRowSum(matrix, N);
row_clone = row.clone();
col= calculateSum.calculateColSum(matrix, N);
col_clone = col.clone();
Arrays.sort(col);
Arrays.sort(row);
int pick = 0;
boolean rowflag = false;
int rowNumber = 0;
int colNumber = 0;
if (row[0] < col[0]) {
pick = row[0];// value
rowflag = true;
for (int i = 0; i < N; i++) {
if (pick == row_clone[i])
rowNumber = i;
}
} else if (row[0] > col[0]) {
pick = col[0];// value
rowflag = false;
for (int i = 0; i < N; i++) {
if (pick == col_clone[i])
colNumber = i;
}
}
> else if(row[0] == col[0]){
> pick = col[0];
> rowflag = false;
> for (int i = 0; i < N; i++) {
> if (pick == col_clone[i])
> colNumber = i;
> }
}
test= test + pick;
if (rowflag) {
matrix = rowUpdate(matrix, N, rowNumber);
} else {
matrix = columnUpdate(matrix, N, colNumber);
}
System.out.println(test);
}
}
我的代码有问题
此解决方案适用于一些低阶矩阵和简单场景，但是，当我尝试涉及 100x100 大小矩阵的测试用例时，许多测试用例都失败了。最初，我认为这是数组大小增加时内存 issue/stack 溢出，但现在我发现这是代码中的一个缺陷，我无法预测最终会引导我到达的正确路径我想实现的最佳解决方案。
我在我的代码中发现的缺陷是，在一种情况下，行和列的最佳值相等。我可以自由选择行或列，但是，这里的问题是，如果我先选择行，它可能会将行的值更新为某个非最佳值，我相信只有我事先知道所有最佳路径会帮助我得到正确答案。
在这方面的任何帮助将不胜感激。
此问题引用了此处提出的问题。
只有在使用高阶矩阵时，我才会在应用上述方法时得到以下输出差异。 编辑：
Output Expected Output
1 5499 1 5499
2 30050 2 30050
3 50778 3 50708
4 36589 4 36509
5 19259 5 19259
6 21367 6 21367
案例 3（我的输出是 50778，预期是 50708） 下面的案例 2 示例数据（我的输出是 30066，预期是 30050）
100 57
5 6 5 10 6 3 9 2 4 7 6 6 8 6 5 6 1 6 9 1 6 8 3 7 3 2 4 8 7 8 3 6 3 9 4 2 1 8 5 5 1 5 8 6 6 10 5 3 4 7 3 3 10 10 3 1 7 3 8 4 4 9 3 7 6 7 9 3 2 2 2 4 8 9 8 1 10 6 6 10 7 5 5 7 9 8 3 2 3 3 9 6 3 7 5 5 10 3 3 3
7 6 2 3 8 8 3 10 1 8 4 7 5 2 9 5 3 5 4 6 4 10 1 6 1 5 1 6 4 9 6 4 10 1 2 4 8 10 5 9 1 9 1 9 3 10 9 9 6 5 6 5 9 4 1 4 9 8 6 9 1 3 1 4 9 2 3 4 1 6 4 1 1 8 2 5 10 1 1 10 7 8 7 3 9 3 10 3 10 5 8 3 7 9 10 5 7 3 2 3
4 5 4 6 9 6 6 3 6 3 2 4 9 3 3 6 10 6 3 6 7 7 9 8 9 3 6 6 3 4 9 6 2 5 9 9 9 1 5 1 7 4 9 7 10 3 1 8 1 9 9 3 1 4 6 1 8 10 3 1 10 5 9 4 3 6 8 8 1 3 5 9 1 9 9 4 3 5 1 7 1 1 9 2 1 9 7 4 7 8 7 3 3 9 6 9 10 7 10 5
2 9 4 3 4 5 6 8 5 5 8 2 3 2 1 2 5 1 10 6 5 6 6 8 4 8 3 6 6 3 3 1 6 3 3 7 6 4 2 7 1 5 9 8 9 5 8 8 10 8 8 8 10 7 3 1 8 6 7 2 2 5 9 8 10 10 10 3 2 6 8 9 6 10 6 10 5 10 9 7 6 4 5 6 4 8 7 10 3 5 9 1 5 7 5 5 9 9 3 10
10 2 1 8 2 2 7 3 6 8 10 8 4 1 3 9 3 8 4 8 7 5 4 1 5 3 2 1 6 3 8 8 8 9 10 4 8 10 9 1 4 1 5 5 9 2 1 2 4 1 3 7 5 8 7 2 5 1 2 2 5 4 4 2 3 2 9 6 5 3 6 5 2 6 9 3 4 7 9 4 1 8 5 10 3 1 3 6 8 8 6 3 1 4 8 6 2 6 6 1
2 7 3 9 10 8 5 8 1 1 7 6 2 3 4 1 2 3 9 2 2 1 2 2 7 10 8 4 4 9 9 6 3 9 9 4 8 2 5 3 1 2 9 1 2 3 1 9 4 7 7 1 10 8 9 9 6 7 5 2 8 3 1 1 7 4 8 7 10 9 10 7 9 4 10 8 4 10 1 1 10 2 2 9 8 8 1 3 4 2 10 2 2 3 3 7 4 6 6 1
4 1 5 9 2 7 3 9 5 8 8 5 1 7 1 10 1 3 1 4 2 3 7 1 4 3 5 5 8 5 6 10 2 10 6 2 1 10 9 2 3 8 2 6 9 3 2 1 4 9 6 6 7 1 6 1 8 6 1 4 10 10 2 3 1 9 9 2 9 1 5 8 8 1 10 10 8 1 1 7 4 7 7 2 9 8 1 5 10 10 3 5 6 10 4 2 10 6 10 9
5 3 3 7 7 4 10 4 6 4 3 4 5 6 4 1 4 3 3 2 1 5 1 1 10 3 3 8 6 9 9 6 10 3 3 1 6 9 2 8 7 1 7 10 8 4 7 5 8 4 9 10 9 8 4 4 3 2 4 3 10 10 5 7 8 1 9 3 8 1 4 9 3 5 9 1 3 4 8 10 5 2 4 5 2 7 5 5 1 2 9 6 1 2 3 10 4 5 9 9
10 10 2 7 10 9 2 1 3 4 6 10 5 1 10 7 3 5 7 9 8 9 4 7 6 4 8 3 9 10 9 1 5 5 7 7 10 8 6 3 9 4 2 6 6 7 5 2 1 4 6 9 3 5 9 5 8 6 8 2 1 3 6 2 2 4 5 1 1 10 2 1 6 2 10 8 3 3 6 1 2 1 4 10 4 6 6 9 7 6 7 8 2 7 9 3 9 10 1 5
9 3 4 4 8 4 9 1 1 9 7 4 8 1 5 3 2 3 5 4 7 2 6 6 9 5 8 5 2 4 1 3 2 5 7 6 2 8 3 6 10 10 3 3 8 2 4 10 3 4 10 8 2 3 5 2 10 9 3 4 3 4 6 7 6 8 7 3 7 3 1 4 2 4 5 2 5 5 10 4 1 1 7 1 9 6 5 5 7 2 8 2 6 2 10 10 4 3 1 10
6 2 4 7 3 7 4 4 8 1 6 1 9 5 3 2 6 1 7 1 4 8 4 4 1 1 4 8 1 4 5 2 4 2 6 7 3 2 9 5 5 3 3 1 7 10 4 9 10 4 2 4 6 3 4 1 1 7 3 1 2 10 7 9 3 2 8 7 1 1 5 8 7 9 7 8 9 5 1 6 7 6 6 2 10 4 4 8 10 7 4 4 10 5 6 1 9 4 5 4
5 1 2 3 4 6 10 8 1 3 2 3 7 10 4 2 5 10 5 10 8 4 8 5 2 3 2 7 10 6 8 2 1 6 9 1 3 6 8 9 8 7 3 7 2 5 2 7 3 2 5 3 1 5 1 5 4 2 4 4 6 7 5 1 9 6 1 6 5 6 6 7 4 3 1 9 8 6 2 1 8 5 7 7 7 9 1 1 10 6 4 4 1 8 3 10 6 7 1 5
4 6 7 3 8 1 1 7 8 10 8 4 9 7 7 3 4 2 10 6 5 6 2 9 8 2 9 7 10 6 3 3 1 1 3 3 2 7 4 8 4 5 3 7 9 1 5 7 2 4 9 5 4 4 1 10 3 7 6 9 3 8 10 5 5 5 1 4 2 10 4 9 5 5 1 7 6 3 3 8 6 6 10 6 5 10 9 4 10 10 10 6 6 7 8 3 4 1 10 9
8 2 8 2 3 2 4 1 8 3 5 9 8 6 6 9 1 4 2 1 7 3 5 9 1 8 2 5 1 1 5 7 5 9 9 1 10 3 6 1 2 10 9 3 1 10 2 4 10 6 8 6 9 10 7 5 10 10 9 6 8 2 5 9 3 2 4 9 8 8 9 3 5 10 8 1 3 3 2 7 2 1 5 10 10 3 10 7 4 8 9 4 6 2 5 4 8 9 10 4
9 7 3 9 9 9 2 3 6 6 2 1 9 10 6 4 2 10 8 7 8 9 3 10 9 5 6 2 5 1 10 1 4 4 10 6 6 8 4 6 8 9 3 1 4 4 10 1 3 7 6 7 5 6 7 9 4 6 6 6 8 2 8 9 7 4 6 9 7 10 8 6 9 3 6 6 5 3 3 8 10 3 9 1 3 8 5 2 8 10 8 7 5 6 10 7 6 5 9 9
7 9 6 1 8 4 8 8 9 2 10 7 1 4 6 4 5 5 5 10 3 10 8 3 7 1 4 9 10 6 10 3 9 2 8 3 8 4 6 4 8 3 4 4 10 1 1 5 10 2 8 8 4 2 4 6 5 5 9 1 5 10 1 3 5 5 10 9 7 1 1 5 4 6 4 3 10 5 3 2 3 2 10 1 3 7 10 6 8 2 8 8 8 7 6 10 9 4 5 6
2 4 9 1 1 7 2 3 6 10 5 3 9 4 9 1 1 2 8 7 3 2 8 6 4 2 10 7 7 5 1 5 8 9 7 5 8 2 10 8 8 8 9 10 7 1 2 2 5 4 9 10 1 4 4 9 8 6 8 7 2 3 4 1 8 8 1 3 4 7 4 10 2 10 7 7 6 8 7 9 4 6 10 8 2 6 2 7 5 5 4 7 9 10 2 7 3 3 3 4
10 7 9 5 7 10 3 7 6 10 7 4 3 3 1 1 1 7 1 2 8 9 5 2 7 6 6 5 5 5 10 3 4 9 6 9 2 3 3 5 1 9 2 2 5 9 5 7 3 6 4 7 5 1 10 2 3 5 6 6 5 4 1 4 9 3 3 7 8 2 1 7 1 6 1 10 4 6 1 6 10 6 7 2 9 7 4 2 8 2 2 7 6 3 3 3 5 2 1 10
3 9 4 1 8 1 1 3 5 6 7 3 4 8 1 7 6 2 2 3 7 1 7 1 7 8 10 8 7 6 10 7 9 10 9 9 9 2 10 3 8 5 10 7 9 10 7 8 9 4 3 5 7 10 10 6 4 10 1 9 8 1 6 5 9 8 10 4 9 10 7 9 8 8 1 7 4 7 9 3 4 5 7 1 3 6 5 1 9 3 3 10 4 2 5 10 7 9 5 2
1 6 8 8 4 7 6 5 6 6 3 6 10 4 6 5 7 9 1 1 2 4 3 6 10 1 10 8 7 1 1 7 9 1 4 7 7 4 6 6 6 7 10 3 5 5 8 3 4 10 7 1 1 1 6 4 5 1 9 6 7 2 8 3 8 3 1 2 7 7 4 6 8 9 7 4 7 3 6 1 5 4 10 5 6 3 4 10 8 6 8 8 5 3 10 1 4 1 8 5
4 3 2 2 10 4 7 10 6 8 9 2 2 7 7 10 3 6 9 6 3 1 5 10 8 4 10 2 9 3 1 5 9 4 7 8 5 1 1 1 5 2 9 4 7 4 4 6 6 1 8 10 6 5 10 9 9 10 5 5 4 3 9 2 9 3 3 4 4 8 2 1 9 8 10 1 2 7 4 4 9 2 9 2 4 9 8 6 6 8 7 3 10 6 7 1 2 7 5 6
4 3 10 5 4 6 6 1 3 7 5 5 2 4 9 6 3 7 4 7 1 10 7 10 5 6 9 2 3 6 6 3 6 8 5 7 1 5 5 6 2 7 8 4 5 4 2 7 1 5 6 4 6 7 8 3 3 7 8 10 1 4 9 10 2 1 9 5 8 8 8 4 1 9 4 4 10 4 4 4 3 10 9 7 9 4 3 7 10 7 7 9 4 10 6 5 6 6 9 7
3 8 7 1 7 2 9 5 5 6 2 10 10 8 3 10 3 1 4 6 1 8 6 10 9 7 5 3 9 10 3 5 5 1 5 10 4 4 6 3 7 8 9 4 1 10 10 5 6 10 10 1 9 9 1 9 9 3 9 10 9 3 5 1 9 9 4 8 4 3 4 6 10 10 7 6 8 9 2 9 6 7 5 3 8 7 4 7 8 2 5 4 6 8 7 1 8 9 2 6
8 7 7 2 6 7 1 2 4 10 3 1 2 5 10 8 6 9 9 6 4 10 5 4 3 2 10 9 2 9 5 5 4 5 9 8 10 7 8 3 8 4 7 1 10 2 2 7 1 7 8 9 7 9 2 6 3 5 5 3 6 1 2 10 4 2 5 5 4 8 4 1 4 3 10 1 1 8 8 4 5 2 3 4 6 3 7 9 4 5 7 8 4 5 3 5 10 7 8 8
1 6 9 9 8 6 4 9 8 2 2 1 10 6 7 4 8 8 2 2 1 4 3 3 5 7 6 6 5 9 9 10 1 5 7 3 6 4 1 9 10 4 10 8 8 5 7 10 7 8 7 10 6 8 6 6 10 3 9 9 5 3 3 9 5 1 5 8 5 5 7 1 2 7 5 9 9 6 9 3 10 1 1 2 5 9 7 5 3 6 8 4 1 3 3 10 1 10 6 5
8 7 10 8 1 1 5 10 2 9 6 4 8 7 8 3 6 3 2 5 8 2 2 6 6 9 9 4 8 1 8 9 2 4 3 4 2 8 6 1 5 10 4 10 3 3 5 2 1 9 3 5 3 6 7 10 1 5 10 3 3 6 4 9 1 6 4 4 8 7 1 7 9 9 6 3 4 6 5 4 4 4 1 3 9 5 2 2 9 8 7 6 5 10 3 6 4 8 7 8
1 1 9 9 9 9 8 4 7 1 4 5 9 9 9 1 5 7 3 4 6 6 7 4 5 4 9 2 7 10 7 9 8 2 7 8 9 10 8 10 5 8 5 9 10 3 2 5 5 9 4 8 3 8 3 10 10 9 7 5 6 10 10 10 4 3 1 5 9 1 9 3 6 3 1 4 7 10 10 10 8 7 10 6 1 2 6 7 2 10 4 2 5 3 9 6 9 6 5 2
10 2 9 4 9 4 9 1 6 1 5 3 5 10 6 7 1 4 1 7 9 1 1 4 7 7 8 10 7 3 5 3 5 5 4 8 7 1 7 4 8 7 10 3 7 3 2 6 8 9 4 9 2 6 6 4 3 7 6 5 3 2 1 4 6 1 6 3 6 4 1 4 4 5 8 1 7 2 3 6 10 1 4 3 4 3 5 1 6 1 3 9 5 8 2 3 3 3 8 2
8 3 5 7 6 6 6 4 8 9 8 10 7 4 5 10 4 9 10 2 2 5 6 4 10 6 6 2 4 8 9 2 10 3 5 5 7 1 7 6 8 4 2 3 5 5 3 5 7 2 4 3 8 5 9 1 4 8 5 5 7 4 2 4 10 1 2 7 10 3 7 10 6 9 8 3 2 7 2 2 5 3 5 8 10 7 3 5 3 9 3 10 9 1 2 8 4 2 1 10
7 3 5 8 8 6 5 5 9 8 4 2 2 8 2 6 7 8 8 6 6 10 8 6 3 4 5 1 3 10 5 8 2 4 6 5 7 9 7 10 9 4 1 3 2 1 3 10 9 3 8 7 9 1 2 1 10 8 3 1 3 7 2 10 10 8 9 4 4 5 1 2 6 6 9 2 8 7 5 7 9 7 6 5 7 1 4 6 10 4 7 3 8 5 10 8 4 8 8 7
1 2 1 2 6 8 4 2 1 6 7 5 7 9 7 8 9 9 1 10 6 9 2 4 10 1 9 8 7 3 7 3 3 6 4 4 5 6 10 4 9 6 9 9 4 1 3 8 4 2 3 5 4 7 7 1 10 2 1 4 5 2 4 10 4 10 1 6 2 6 3 9 8 4 4 8 3 1 7 10 9 5 5 2 1 6 3 4 4 8 7 9 9 6 6 10 8 7 8 10
4 1 9 4 5 6 6 10 9 6 7 5 8 1 3 9 5 10 6 7 7 10 8 8 9 4 3 4 3 6 1 9 5 10 5 8 4 10 7 4 2 6 6 10 6 4 4 3 5 8 6 4 2 4 8 3 7 4 2 9 1 1 6 2 6 1 5 6 7 10 6 2 6 6 3 4 10 2 1 1 8 5 6 7 5 3 8 10 2 10 6 2 6 9 1 8 5 7 1 1
3 3 2 1 7 2 4 1 3 2 2 8 4 7 1 2 2 10 4 9 8 9 10 8 2 9 9 6 10 2 5 2 8 8 10 7 6 10 1 7 3 8 4 7 9 7 1 7 2 4 6 5 4 1 2 10 8 4 9 7 10 5 8 2 8 7 6 2 9 8 5 6 3 5 10 10 9 6 6 3 1 7 9 10 10 1 3 8 3 3 9 1 2 3 8 6 5 7 10 8
9 8 6 2 10 4 4 4 10 9 2 5 1 1 9 7 3 8 9 8 6 10 5 9 5 4 1 6 2 9 9 4 9 6 10 5 6 3 3 2 2 2 4 4 2 5 5 6 10 7 10 5 1 5 10 9 9 2 6 10 2 5 7 5 8 3 4 3 4 8 4 5 7 7 10 4 7 7 2 6 8 9 4 5 6 9 3 9 3 8 1 10 4 3 5 7 4 5 1 10
3 1 2 9 7 5 1 1 8 4 7 6 7 10 1 6 7 3 4 2 7 10 8 4 7 8 10 5 1 9 4 3 10 9 9 9 1 5 7 8 10 6 5 2 10 9 4 2 6 4 5 9 10 8 10 2 1 4 5 10 7 2 3 9 9 9 2 9 4 3 2 10 6 1 9 8 5 1 5 2 7 1 3 1 9 4 7 1 4 6 8 8 10 9 1 8 7 1 5 2
7 7 7 10 2 10 3 7 1 4 7 1 7 6 6 6 10 4 5 2 1 9 3 1 10 2 1 7 7 1 10 3 3 1 1 2 3 8 2 8 7 6 3 6 6 10 5 8 6 1 10 7 7 1 10 8 4 4 1 7 3 2 10 8 6 2 1 4 4 5 6 7 4 9 1 5 5 1 1 9 5 5 8 1 3 3 9 8 2 10 8 9 2 9 6 8 3 3 3 3
2 8 4 9 5 7 10 5 9 10 2 7 8 1 2 4 10 2 4 1 8 4 3 2 9 7 8 7 10 8 1 5 9 4 5 10 5 10 2 10 10 2 2 2 1 3 1 3 4 1 6 9 7 4 8 4 10 9 8 3 2 8 1 10 4 8 1 8 6 1 5 8 4 2 2 7 7 2 2 5 4 1 7 1 8 7 10 1 10 1 10 9 9 10 1 7 6 1 6 7
6 2 1 6 5 7 2 9 6 10 6 4 3 7 7 9 9 8 7 1 7 7 8 2 5 7 1 10 7 6 2 1 5 10 10 7 2 8 9 10 9 9 1 1 3 10 2 6 3 8 4 2 9 6 7 5 5 2 7 4 7 9 5 1 7 1 5 3 1 4 5 10 7 6 7 8 6 5 8 2 1 10 8 2 9 4 3 10 10 8 5 8 6 3 2 1 4 4 9 3
3 10 6 5 3 9 10 8 5 1 3 4 9 4 8 10 2 7 6 8 6 1 1 3 3 8 5 7 10 4 7 5 2 2 4 10 5 4 9 6 4 5 9 6 10 7 6 7 6 7 1 3 8 5 1 1 4 2 4 10 1 4 5 10 5 9 2 6 7 2 3 1 3 1 1 9 2 5 1 10 10 2 4 10 3 6 2 6 4 5 9 8 7 9 8 9 8 2 3 9
7 10 4 1 3 6 10 7 1 2 6 8 9 9 4 2 3 6 2 1 4 6 9 1 6 7 6 10 4 6 6 4 7 8 6 7 5 8 6 10 10 7 5 7 10 10 7 1 10 10 4 2 10 9 2 5 3 9 8 2 2 7 9 4 8 4 10 3 8 9 9 1 8 4 9 4 3 7 7 9 1 8 7 8 3 6 6 1 2 1 6 5 9 5 3 1 6 2 6 10
10 5 5 3 9 10 6 5 3 6 5 4 7 9 6 10 7 5 5 2 10 9 6 9 7 9 9 3 5 5 9 3 4 4 7 3 9 8 1 6 3 2 8 5 6 6 8 3 6 8 7 7 4 2 4 6 10 4 6 8 5 4 7 5 1 2 9 9 6 5 10 9 4 10 4 8 6 4 9 2 1 5 1 7 3 3 5 1 3 7 8 1 2 10 9 2 4 5 3 2
9 5 1 3 7 10 10 9 9 3 8 3 8 5 4 5 3 3 5 7 9 7 5 8 3 6 5 2 6 3 8 6 8 10 8 2 8 3 2 7 1 8 9 3 4 3 3 4 1 5 2 10 4 7 7 7 3 5 8 3 1 2 8 8 7 5 9 4 6 9 5 3 7 8 1 1 1 5 2 1 10 7 3 8 8 4 3 6 3 6 4 1 8 3 7 4 8 10 10 3
1 10 10 7 3 3 10 3 8 2 5 2 8 4 9 3 8 9 10 5 7 1 6 10 9 2 2 2 10 7 8 2 6 1 8 4 7 3 6 3 7 6 8 5 4 5 5 7 8 9 5 9 8 4 6 9 5 9 8 5 7 7 3 10 1 9 10 3 4 9 10 9 6 4 9 6 6 5 7 4 7 4 6 10 3 9 4 5 7 3 2 9 3 1 1 3 1 10 7 10
6 10 4 9 6 8 3 9 1 6 7 9 1 7 6 5 1 1 3 2 10 7 9 5 8 8 8 8 9 3 3 6 4 8 2 4 3 9 5 1 8 5 9 9 8 2 5 10 10 6 4 4 6 9 9 3 1 5 8 1 7 7 6 4 10 2 3 5 8 8 8 2 10 1 5 2 4 2 2 9 4 7 9 4 3 1 3 9 7 6 6 7 8 2 2 5 5 6 4 4
5 10 2 9 9 7 7 6 3 4 2 6 7 3 6 3 4 3 1 4 9 5 4 6 9 8 8 5 4 4 1 9 6 10 8 8 2 2 8 7 5 3 2 6 3 6 2 5 2 9 5 8 2 9 10 5 6 1 2 5 8 6 2 10 8 2 9 5 10 3 10 6 3 3 1 10 8 9 5 2 1 9 2 3 6 5 5 8 10 9 2 10 7 2 8 5 7 4 7 9
8 9 4 1 6 1 3 9 10 8 7 1 5 8 9 2 7 6 3 6 3 5 8 7 6 1 3 6 7 2 6 8 7 6 8 8 4 4 8 9 5 3 9 1 5 4 6 5 9 1 8 2 7 1 9 6 5 7 9 7 1 1 6 3 1 6 2 6 10 2 4 7 2 3 9 8 7 9 2 6 7 6 8 7 9 4 4 8 8 4 4 2 10 7 8 5 1 7 1 1
5 3 4 7 4 4 4 9 10 4 8 5 2 6 4 5 2 9 5 10 5 8 10 2 7 7 2 2 4 10 2 8 6 4 7 1 2 3 2 1 6 6 10 4 3 9 5 1 4 3 6 7 1 10 10 10 3 4 9 4 2 4 2 8 10 5 8 7 5 2 9 2 2 1 8 4 8 2 9 8 5 5 6 5 2 7 4 2 2 6 9 6 5 4 3 5 6 4 6 8
2 7 5 10 10 8 10 6 4 10 10 2 8 9 8 5 1 4 2 2 4 10 4 8 7 8 10 8 7 4 5 7 10 3 5 5 6 4 10 4 10 4 6 7 3 6 6 7 3 10 2 3 6 1 5 1 2 2 6 4 4 1 7 6 6 7 8 1 8 3 9 4 7 10 7 1 6 7 5 6 4 7 3 3 10 3 4 7 2 1 6 2 5 9 7 7 3 7 1 8
5 2 10 8 2 4 1 5 6 2 7 6 2 2 10 2 9 8 1 5 2 5 8 1 9 10 3 3 2 3 2 5 4 6 4 1 5 6 5 5 8 9 9 8 3 2 5 3 10 9 5 3 4 9 8 3 10 5 5 6 2 1 1 8 9 1 6 9 4 10 1 1 10 8 9 8 2 5 2 4 10 6 3 10 10 6 6 7 2 7 7 9 10 7 7 7 10 9 10 10
8 7 4 10 6 3 7 3 7 6 4 9 10 4 7 4 8 6 2 9 5 4 6 2 3 5 1 6 10 2 5 7 7 8 2 1 3 3 9 6 3 2 10 3 5 4 7 1 2 5 9 5 9 7 10 8 10 6 9 8 3 6 8 10 2 9 1 4 5 7 1 10 7 2 1 3 6 9 2 1 6 1 9 8 9 3 4 3 2 1 2 6 9 3 1 10 3 7 9 3
1 9 8 10 4 5 1 9 6 4 1 5 7 8 4 1 7 5 8 1 5 7 6 2 2 5 3 2 2 8 4 9 1 9 2 8 6 3 6 8 2 2 2 8 8 6 9 7 5 4 4 10 5 8 7 2 7 10 2 4 7 10 4 5 3 1 8 9 5 9 4 10 7 6 3 5 7 3 8 9 5 10 1 5 2 4 6 5 7 10 8 1 5 10 10 5 3 7 3 3
8 9 6 6 9 10 5 8 1 1 2 9 9 9 2 6 1 3 2 9 4 4 1 9 5 2 8 1 5 10 3 8 3 7 10 5 4 10 8 5 10 4 4 9 6 7 1 10 10 2 6 4 5 1 1 10 10 8 2 5 1 1 3 7 5 6 2 8 4 9 8 3 10 6 2 5 3 3 8 10 2 7 9 5 9 7 9 2 1 3 10 7 1 9 7 10 1 1 2 6
6 10 1 5 10 1 4 5 10 5 4 2 2 8 4 2 4 7 7 9 1 5 7 5 2 1 3 6 6 5 5 5 10 7 7 6 10 9 10 3 9 3 2 10 8 9 9 3 5 9 8 4 3 9 3 1 4 1 9 4 3 3 3 2 1 3 1 4 1 5 3 4 5 5 10 2 7 10 9 2 5 6 1 9 4 6 4 10 1 9 4 8 6 1 10 6 7 4 5 5
1 6 6 9 5 3 3 6 5 9 1 2 1 4 9 4 7 9 2 7 10 9 7 6 4 2 5 3 9 6 7 2 5 3 1 3 5 4 5 3 3 7 10 7 3 7 7 5 7 7 6 3 3 9 1 10 7 3 10 7 4 4 3 6 8 1 8 4 7 9 8 10 3 2 6 2 6 8 5 1 7 2 8 2 2 5 5 5 7 6 8 3 10 1 8 9 7 5 8 3
8 2 5 2 9 6 8 2 10 8 2 10 3 9 9 7 6 1 1 3 7 3 2 10 5 1 5 7 4 1 3 6 9 6 9 3 8 3 6 10 2 4 9 9 10 7 5 8 7 2 1 5 9 2 1 2 2 8 5 10 8 6 8 7 7 9 6 6 1 6 3 5 9 8 1 1 5 10 8 9 9 4 2 5 4 7 7 3 3 8 6 3 4 9 10 8 4 7 8 10
10 10 3 5 7 4 6 7 10 2 6 3 8 9 8 3 10 5 9 2 6 9 4 3 6 3 10 1 7 2 9 4 7 4 8 2 7 8 4 8 8 2 4 5 4 10 7 9 1 2 3 9 2 4 6 2 10 7 3 9 6 4 3 6 6 4 6 9 8 2 2 2 7 2 6 6 6 4 9 8 2 1 7 5 5 10 10 9 10 6 10 3 7 7 8 3 6 4 6 8
8 7 3 4 1 6 9 7 6 10 10 10 10 2 9 1 10 10 9 9 2 6 9 4 5 6 3 6 1 5 1 3 2 5 2 6 9 4 5 4 6 9 10 5 5 2 9 1 8 10 8 6 7 6 7 10 1 10 9 5 9 6 8 7 10 7 10 6 10 1 1 4 3 4 2 5 2 10 10 7 9 7 7 3 6 8 4 1 1 5 3 10 7 3 8 5 3 5 5 1
3 2 3 8 5 8 2 10 6 9 8 9 7 7 8 4 10 2 5 4 4 5 8 4 8 5 1 6 3 9 8 6 6 1 1 1 8 9 5 7 8 8 8 3 9 5 10 7 5 2 7 4 4 4 8 8 10 9 6 1 8 5 10 9 1 6 4 4 2 3 6 9 5 4 8 6 4 1 5 2 7 5 8 2 1 1 10 1 5 7 9 9 5 1 5 8 10 10 5 1
10 6 8 10 9 4 8 3 4 10 8 6 4 6 7 6 10 7 10 4 7 6 7 9 3 1 9 2 5 4 2 5 7 1 3 5 5 2 1 7 8 8 1 7 2 9 5 6 3 1 2 10 1 1 7 3 5 8 9 6 7 9 9 8 2 7 3 10 1 8 5 3 7 3 4 6 4 1 2 8 3 9 2 9 1 8 7 6 1 6 4 2 7 7 9 5 10 1 2 2
1 1 4 4 8 1 1 8 5 8 5 4 4 10 1 1 4 10 10 5 8 6 3 8 8 4 3 9 1 9 2 6 9 6 4 1 1 1 5 10 5 3 1 10 4 8 7 3 9 2 1 3 4 10 5 6 4 9 5 2 1 4 4 6 8 6 10 10 6 8 4 4 3 1 4 2 5 9 1 2 4 4 2 6 10 1 7 4 9 4 8 3 5 4 1 1 5 4 10 1
7 1 5 2 10 5 8 2 1 9 7 4 6 1 6 9 1 8 7 3 9 3 5 5 3 2 7 8 5 7 3 2 1 9 3 10 8 9 1 3 1 1 8 1 9 1 8 2 3 1 5 7 8 6 8 6 10 4 8 3 2 3 8 3 7 9 1 6 7 2 7 3 1 10 8 3 7 6 6 8 3 10 5 4 8 1 2 1 2 8 6 9 3 10 7 10 1 4 9 3
8 9 10 1 7 5 9 10 5 4 6 4 7 1 1 5 1 8 6 7 10 10 4 9 1 5 3 10 2 5 9 1 6 1 4 7 2 4 1 9 1 9 5 9 6 10 3 6 2 4 9 1 6 5 10 8 5 10 7 10 5 8 1 9 3 10 5 6 1 8 6 1 7 8 10 7 1 8 8 2 5 4 9 1 10 6 4 6 6 3 4 7 10 6 7 9 3 7 3 1
4 4 8 7 10 5 2 5 7 1 10 7 10 7 9 3 3 10 2 7 5 4 4 2 1 8 9 4 5 9 6 10 7 5 5 6 2 2 1 8 2 3 4 2 10 6 3 2 3 3 5 7 7 4 4 4 10 2 10 9 4 5 8 8 8 8 3 1 3 9 10 10 7 6 7 10 4 10 1 9 8 9 8 2 10 6 5 4 8 5 10 10 8 3 1 9 10 10 3 2
4 8 6 5 4 1 5 4 5 8 9 10 7 10 2 5 5 7 9 4 6 5 8 3 2 8 4 2 5 4 2 2 9 4 6 8 9 3 6 10 8 6 3 7 9 5 1 6 5 4 7 5 5 8 3 1 3 1 1 9 5 3 1 3 8 10 10 4 5 5 4 6 1 2 6 7 8 9 10 2 6 2 9 7 1 4 10 8 7 6 6 4 1 10 8 6 8 2 7 8
7 10 5 9 10 5 6 4 6 9 1 10 4 7 6 1 5 6 3 6 1 7 7 5 6 3 8 6 5 5 2 6 4 6 4 7 1 5 1 10 8 4 4 4 9 5 4 1 6 7 7 3 8 1 5 10 10 2 10 2 10 10 10 6 8 3 3 8 7 7 4 10 1 2 5 9 5 1 7 10 4 1 9 10 7 2 7 3 2 9 2 7 1 3 1 9 2 4 7 6
5 8 9 8 2 9 2 10 4 2 5 5 1 9 7 2 7 3 1 5 9 10 6 10 5 10 2 8 7 1 7 2 1 4 1 9 10 3 4 5 1 2 6 4 9 3 5 3 7 4 10 5 9 3 3 7 8 2 3 3 6 3 9 4 4 7 7 1 4 4 10 2 3 6 5 4 7 9 1 4 7 7 8 5 7 7 10 10 7 10 6 8 9 6 5 5 2 6 5 4
3 6 4 10 5 4 9 8 10 6 7 5 9 6 10 3 5 5 6 7 6 10 1 9 5 3 5 3 9 2 10 7 2 8 1 5 9 9 5 10 10 7 5 9 5 6 9 9 6 2 9 5 7 8 10 3 6 7 5 2 8 5 1 9 6 8 2 6 7 1 7 9 7 6 7 5 5 5 2 8 9 9 5 3 5 1 5 10 8 5 4 5 2 10 3 8 8 4 4 5
3 4 9 6 3 8 9 1 3 4 9 10 8 1 4 1 5 6 10 8 9 2 4 1 9 4 1 6 8 8 9 10 2 5 2 9 4 5 2 7 1 1 6 10 6 8 10 6 4 10 10 10 6 3 6 4 4 8 6 2 7 1 9 2 6 7 8 3 10 6 4 9 5 6 3 6 1 5 9 7 4 9 6 1 8 8 2 5 1 5 5 10 7 5 5 1 9 3 1 10
7 6 8 10 3 6 5 10 3 2 7 5 8 9 10 6 7 2 9 7 6 2 7 1 6 5 1 8 7 8 2 10 5 5 9 8 1 7 5 2 8 7 9 6 5 4 5 6 10 2 4 9 10 4 9 6 7 2 2 5 1 5 9 3 9 4 5 4 9 5 3 6 9 1 3 5 1 1 9 1 4 7 6 8 5 10 5 5 1 1 2 10 2 4 2 4 10 1 9 4
6 4 8 5 6 6 1 6 7 2 3 4 4 2 8 6 5 10 4 10 2 2 10 3 6 5 10 3 10 7 3 5 10 4 4 3 10 7 6 4 4 3 6 8 5 10 3 2 1 1 7 6 1 6 10 5 2 9 7 3 2 7 1 10 6 2 10 10 3 10 5 3 7 1 8 9 7 5 1 4 5 3 6 4 1 6 10 10 10 10 9 3 6 6 4 4 10 1 4 5
6 8 8 1 8 4 6 1 4 5 3 7 10 5 3 4 10 10 10 5 3 7 5 10 3 4 1 4 5 6 5 4 6 7 7 6 6 2 8 10 1 7 9 1 1 4 10 4 7 1 5 10 1 3 5 1 5 5 2 3 5 1 2 8 1 8 3 8 5 8 5 9 5 10 4 1 7 10 5 7 5 9 5 5 1 8 7 5 6 2 1 6 4 2 7 7 1 8 1 4
6 3 3 3 1 10 10 5 7 1 2 2 3 3 6 9 4 4 2 4 7 4 6 9 8 7 5 2 4 5 9 1 9 7 2 5 10 10 4 10 7 6 5 9 2 7 1 2 2 10 9 10 2 10 3 6 5 10 3 5 2 1 3 10 7 5 10 5 5 4 8 9 10 7 4 2 9 10 1 7 5 5 1 3 7 3 2 9 6 4 1 7 4 7 5 10 4 7 10 10
5 3 2 8 10 3 3 1 4 1 4 10 3 10 6 10 8 9 5 7 9 4 5 4 3 3 3 10 3 7 9 10 7 3 9 3 4 6 6 10 10 10 5 6 7 3 4 1 1 1 7 2 3 5 4 7 4 8 4 8 2 1 6 1 5 6 8 5 8 4 2 10 10 8 4 5 4 5 6 3 8 7 1 1 1 3 9 10 1 10 5 1 7 5 6 1 9 10 10 2
7 3 10 2 10 4 9 4 5 3 5 10 10 8 1 4 5 2 1 4 1 9 9 7 1 5 6 7 4 9 4 9 6 4 5 9 2 5 8 8 2 10 9 4 10 4 10 6 3 5 1 4 2 7 6 3 4 8 1 9 10 1 4 7 3 5 4 8 2 1 8 8 5 3 10 8 4 9 7 1 3 6 5 1 2 4 7 1 6 8 5 5 8 7 5 6 9 7 7 3
7 5 7 10 5 2 8 8 6 2 10 7 9 2 6 10 7 8 3 3 10 4 5 9 8 10 9 10 6 5 6 1 10 3 4 6 5 6 8 3 7 7 9 7 7 10 4 3 7 2 3 3 3 5 10 3 3 10 1 4 7 1 8 2 9 8 7 9 4 10 1 7 1 9 7 6 3 9 3 10 3 3 10 4 4 8 6 10 4 9 7 6 2 3 7 6 3 5 4 9
6 6 3 7 5 4 2 1 5 10 6 9 9 3 3 5 6 9 10 6 5 1 6 1 3 1 5 7 8 3 1 3 4 10 5 2 1 8 6 2 3 6 1 7 5 7 4 5 4 3 9 1 10 4 9 4 4 7 8 6 1 9 6 1 1 7 10 3 8 6 5 10 10 10 9 10 3 5 8 7 3 2 9 4 9 6 3 2 5 3 10 4 9 8 3 9 3 6 9 8
2 8 1 3 5 10 1 6 7 5 6 10 4 6 1 8 5 1 7 3 4 1 6 4 10 6 3 6 9 8 2 5 4 7 7 1 7 4 8 1 4 7 7 2 10 5 7 3 9 2 3 4 3 4 2 2 5 6 8 10 2 1 6 1 10 2 9 10 5 10 4 8 8 10 2 5 3 4 8 6 7 9 1 5 8 6 5 9 7 5 2 1 6 2 6 9 10 2 5 7
3 2 4 9 8 4 3 4 2 7 3 4 7 8 7 1 9 8 5 5 7 10 8 4 4 8 5 1 7 10 2 8 2 6 10 1 7 2 6 1 10 6 9 6 5 1 4 5 5 6 3 3 1 9 7 5 8 9 8 4 1 4 8 4 8 10 7 9 2 3 9 4 7 7 8 10 4 1 3 9 9 9 2 5 4 3 4 6 5 6 8 4 7 3 5 2 9 1 5 10
5 9 4 1 1 5 6 9 5 5 3 6 9 10 6 6 6 10 9 5 4 7 2 10 7 2 6 9 10 6 1 4 1 9 1 9 1 6 9 5 5 1 5 5 1 8 7 10 5 3 9 6 3 3 4 6 8 7 5 9 3 3 4 7 6 8 6 9 6 7 7 2 8 4 3 7 9 8 2 6 10 10 10 7 7 7 1 8 3 7 2 2 7 10 7 8 9 6 2 9
5 3 10 1 8 2 4 10 1 9 10 2 4 10 5 5 1 6 4 5 3 4 5 3 1 2 5 6 7 1 6 1 3 6 8 3 4 4 10 1 6 4 8 2 1 4 7 1 9 9 2 7 3 4 6 10 8 6 1 2 6 7 6 8 5 1 7 8 8 8 5 7 6 8 4 4 5 8 8 3 5 8 2 1 6 3 7 4 6 3 6 7 4 4 2 5 4 2 9 7
4 6 5 6 2 5 4 4 8 9 3 7 9 8 5 5 9 9 3 3 2 7 6 1 2 7 9 7 1 8 3 8 2 8 10 9 5 2 10 6 3 8 1 7 8 4 8 8 7 3 5 3 4 7 3 5 3 5 3 5 1 5 2 3 9 5 6 9 1 7 6 2 6 10 8 10 4 4 3 5 6 3 10 2 10 1 3 8 10 8 8 5 1 9 4 10 1 2 3 2
7 3 1 1 1 4 8 8 9 5 8 10 2 10 1 5 6 1 1 5 9 2 8 8 2 6 4 1 1 1 10 9 4 9 7 5 6 4 6 7 2 10 6 1 3 6 2 2 8 3 6 2 7 10 2 1 8 3 6 3 8 2 4 1 3 9 8 8 2 1 9 10 8 9 3 10 7 6 1 2 6 5 1 2 7 8 6 10 10 1 8 9 1 9 3 3 7 9 2 5
7 3 3 7 10 5 6 7 4 10 8 8 3 7 5 9 4 5 4 7 8 4 5 10 4 9 5 10 3 5 9 3 9 8 1 4 6 6 9 8 7 4 5 8 5 7 6 5 2 8 5 9 1 9 8 6 8 9 8 1 4 8 3 2 4 1 7 3 3 3 8 1 4 10 4 6 7 7 10 1 1 4 8 10 2 4 9 6 5 9 8 4 2 6 3 5 6 2 9 3
9 8 4 6 1 2 5 7 2 3 3 10 10 10 9 5 7 6 10 3 6 7 2 9 3 10 10 5 3 1 5 8 1 7 9 8 3 2 1 3 4 7 6 7 10 7 7 1 10 7 1 10 4 5 5 9 10 9 10 6 3 7 8 1 3 5 2 10 5 2 8 7 9 10 10 2 2 8 9 7 1 1 9 10 3 10 6 2 9 1 4 8 8 8 5 5 1 1 10 9
6 2 3 1 8 8 6 1 8 1 4 6 10 7 5 5 5 2 8 10 3 3 2 7 5 5 10 8 9 1 4 1 2 5 7 8 10 8 5 3 9 5 3 6 10 5 10 1 6 3 5 1 10 3 6 8 3 3 4 1 8 3 6 5 4 7 10 1 10 5 10 3 10 1 8 5 3 3 8 10 8 1 5 3 9 8 2 6 8 3 1 6 6 3 3 6 5 8 3 4
7 3 1 10 10 9 5 7 4 6 8 2 6 1 1 9 6 1 7 7 2 2 9 9 1 3 3 6 8 2 3 2 8 7 7 7 5 7 6 4 10 4 7 5 1 5 2 1 5 2 1 5 10 10 7 3 7 8 10 5 7 1 1 2 2 3 1 7 2 4 4 4 4 9 4 1 6 6 9 6 6 7 8 7 2 5 7 2 6 4 3 10 9 9 1 1 8 8 7 2
7 3 6 6 3 9 4 5 7 9 6 3 10 1 7 1 7 4 6 4 2 1 7 3 3 1 7 10 6 7 5 2 7 9 8 8 2 6 6 6 7 1 10 10 6 6 9 5 5 2 2 3 8 5 1 9 7 1 4 7 1 3 4 3 5 10 1 5 10 7 7 6 8 2 9 1 10 1 1 8 1 3 1 4 7 5 7 6 8 7 5 6 1 5 3 10 8 4 1 7
4 5 6 4 5 6 6 1 2 9 7 1 2 5 6 9 2 3 2 5 1 1 1 9 3 1 6 5 3 1 3 10 6 1 2 8 1 3 6 9 3 7 1 5 2 1 5 5 2 4 10 7 6 1 3 3 7 3 10 6 9 9 4 7 2 10 8 4 3 3 8 1 2 1 4 9 8 5 1 7 3 5 6 10 4 8 3 7 9 7 4 4 9 10 6 3 4 2 8 10
7 7 10 10 4 4 2 5 8 6 6 2 2 3 2 3 6 1 4 7 5 1 9 6 3 3 4 10 5 5 1 5 8 2 10 9 3 7 2 2 3 1 5 7 5 2 6 10 4 1 10 10 5 4 8 6 7 7 7 6 3 4 9 4 10 10 10 7 3 1 1 10 3 6 10 5 8 5 4 6 8 3 2 6 5 2 9 3 7 3 2 4 1 7 9 10 4 5 2 6
2 1 6 10 2 3 9 5 4 5 4 8 4 6 3 4 5 2 5 3 3 4 3 4 5 9 7 2 6 3 3 9 9 1 7 7 3 7 7 10 8 8 2 5 10 4 2 3 1 8 5 1 6 3 8 5 8 8 6 5 4 1 2 6 6 7 10 10 4 2 3 9 8 5 10 6 2 3 1 6 4 2 7 4 5 7 2 3 4 5 8 6 8 6 4 1 6 3 3 6
8 8 6 6 6 7 1 2 6 4 4 1 5 5 5 1 9 3 9 2 6 6 5 4 2 3 1 7 5 10 3 9 3 8 8 7 5 4 5 8 7 3 10 1 5 10 7 2 2 9 7 9 2 6 6 2 3 6 7 1 1 2 5 3 4 10 10 4 8 5 9 7 5 8 6 1 7 9 3 10 4 5 6 5 3 9 1 3 9 2 7 2 7 8 9 2 4 3 4 1
4 7 4 3 3 4 7 4 8 6 5 6 4 10 5 10 7 10 8 9 10 6 7 7 9 3 7 4 7 6 3 4 8 6 9 4 7 8 8 4 10 7 10 6 2 4 7 7 3 7 3 3 6 6 8 6 5 10 1 1 8 1 2 4 2 6 4 1 6 4 6 6 5 4 5 6 7 1 5 3 6 8 8 1 10 7 6 7 10 5 2 4 7 4 9 3 3 8 3 6
6 7 2 7 9 9 8 6 1 5 10 9 7 6 6 9 8 3 6 3 3 9 7 1 10 5 2 8 4 5 9 10 8 7 5 7 9 9 1 1 10 5 9 4 6 9 6 1 8 10 2 1 8 3 8 10 8 9 3 3 10 3 2 4 8 3 3 3 8 1 8 7 2 6 3 1 7 9 6 1 10 1 1 7 10 9 7 1 1 10 6 1 3 3 6 8 1 4 5 10
3 5 9 8 7 8 7 5 10 5 9 4 9 8 8 1 4 5 3 4 6 5 10 4 1 10 5 1 8 3 5 5 2 5 10 8 4 5 6 10 10 6 3 6 1 5 9 8 2 10 3 1 2 7 7 8 3 4 9 9 10 5 2 7 1 7 9 3 1 3 3 3 1 3 1 10 1 9 1 7 1 3 2 6 5 3 9 1 2 6 2 8 1 4 6 9 4 3 6 9
4 5 3 3 10 7 1 2 4 4 9 2 10 3 7 3 2 8 5 8 7 7 6 1 3 5 8 1 1 2 9 4 8 10 1 6 1 2 5 6 5 5 7 6 5 2 1 7 9 10 8 8 3 9 1 6 6 3 8 3 7 2 10 7 4 7 8 10 1 9 9 7 9 10 4 5 8 8 2 7 10 6 6 2 1 1 10 9 6 1 6 1 10 3 2 7 9 4 7 3
7 1 4 8 1 6 8 10 9 10 8 2 4 1 4 7 1 5 4 7 8 8 8 5 4 5 8 8 1 5 6 2 1 3 9 4 7 1 2 1 8 8 10 2 5 6 4 1 3 5 10 1 10 6 9 3 7 5 9 3 1 8 1 1 2 7 1 2 1 9 4 8 5 1 6 9 3 8 6 1 5 9 6 9 9 10 1 1 3 7 1 3 6 9 3 4 8 4 10 10
1 7 7 9 3 4 3 3 10 7 1 10 2 10 5 1 4 9 4 8 5 4 10 10 2 1 5 6 7 3 7 9 8 3 10 5 6 5 1 3 5 10 7 2 6 4 3 3 5 2 7 7 2 10 4 9 4 1 7 8 3 6 4 2 8 8 6 2 2 10 7 10 5 7 3 6 5 1 4 7 9 9 2 2 8 5 8 7 9 4 8 3 8 4 10 10 4 7 6 6
6 4 10 9 5 3 7 10 4 8 9 3 1 8 4 3 8 10 6 3 3 2 2 9 5 6 3 10 8 3 10 3 7 9 3 4 2 3 4 8 5 6 7 7 8 7 6 10 6 4 9 10 1 2 1 8 5 3 4 3 9 1 1 5 2 7 9 2 8 9 7 2 5 1 7 1 7 1 2 2 4 8 8 7 10 2 7 8 2 6 7 6 4 6 7 4 9 10 8 6
8 6 7 8 10 9 3 3 10 10 4 9 2 10 3 8 2 7 10 4 4 6 2 5 10 3 10 5 3 7 9 10 6 3 5 8 3 2 9 8 5 9 8 2 9 6 4 5 6 2 10 5 1 7 5 2 4 1 8 1 9 4 1 8 8 3 9 6 3 3 6 6 7 2 6 10 4 1 9 10 2 10 5 4 4 2 3 8 8 2 3 4 7 4 3 5 6 4 10 9
7 10 9 6 9 2 9 1 4 5 8 10 1 5 6 6 2 4 1 1 7 9 7 7 8 10 3 2 5 2 3 9 7 3 8 8 7 7 3 7 1 5 6 8 6 8 8 1 5 3 3 5 6 4 5 4 9 1 9 9 1 4 8 7 4 4 8 6 2 5 9 10 7 3 7 7 4 9 8 10 2 9 1 5 7 7 10 4 5 2 1 6 2 3 5 9 3 8 2 4
这是我找到的算法。它是 O(n^2) 所以它是最佳的。为什么？您必须阅读 n^2 个单元格，以便 OPT 至少为 O(n^2)。
计算所有行和所有列的总和。像这样将它们存储在 class 中：
public class Sum implements Comparable {
public long currentSum;
public boolean isRow;
public int index;
public Sum(long sum, boolean row, int i) {
currentSum = sum;
isRow = row;
index = i;
}
public Sum(Sum s) {
currentSum = s.currentSum;
isRow = s.isRow;
index = s.index;
}
@Override
public int compareTo(Object o) {
Sum s = (Sum)o;
return Long.compare(this.currentSum, s.currentSum);
}
}
算法为：
1. If there is a column or a row which has the smallest sum (i.e. it's the only lowest sum) - choose it.
2. If there are more then one smallest sums:
a)if there are no rows with smallest sum - pick column
b)if there are no cols with smallest sum - pic row
c)Try both out otherwise
将 Sum 存储在 heap 中 - 例如java.util.PriorityQueue。最好自己写堆。它也可以是您要排序的列表，但效率较低。在这里你必须做一些研究，当一半元素递增和一个强烈扩大时，哪种数据结构在求助时最有效。
我已经使用 ArrayList 实现了工作解决方案。随意使用它，但您必须稍微更改代码以提高效率。
//Creates list of all available sums. Sorts them and passes to calculate
public static int solution(int[][] a, int K, int n) {
List<Sum> sums = new ArrayList<>();
for (int i = 0; i < n; i++) {
int rowSum = 0;
int colSum = 0;
for (int j = 0; j < n; j++) {
rowSum += a[i][j];
colSum += a[j][i];
}
sums.add(new Sum(rowSum, true, i));
sums.add(new Sum(colSum, false, i));
}
Collections.sort(sums);
return calculate(sums, K, n, 0);
}
public static int calculate(List<Sum> sums, int K, int n, int res) {
//if (K < 50) System.out.println(K);
int result = res;
for (int i = 0; i < K; i++) {
Collections.sort(sums);
Sum chosenSum;
if (sums.get(0).currentSum == sums.get(1).currentSum && K > 1) {
long low = sums.get(0).currentSum;
int colCount = 0;
int rowCount = 0;
Sum rows = null;
Sum cols = null;
for (Sum s : sums) {
if (s.currentSum == low) {
if (s.isRow) {
rowCount++;
if (rows == null) {
rows = s;
}
} else {
colCount++;
if (cols == null) {
cols = s;
}
}
}
}
if (colCount == 0) {
chosenSum = rows;
} else if (rowCount == 0) {
chosenSum = cols;
} else {
chosenSum = (calculate(copySums(sums), K - i, n, new Sum(rows)) < calculate(copySums(sums), K - i, n, new Sum(cols)) ? rows : cols);
}
} else {
chosenSum = sums.get(0);
}
result += chosenSum.currentSum;
chosenSum.currentSum += n;
for (Sum s : sums) {
if (chosenSum.isRow ^ s.isRow) {
s.currentSum++;
}
}
Collections.sort(sums);
}
return result;
}
public static int calculate(List<Sum> sums, int K, int n, Sum chosenSum) {
for (Sum s : sums) {
if (chosenSum.isRow ^ s.isRow) {
s.currentSum++;
}
if (s.isRow == chosenSum.isRow && s.index == chosenSum.index) {
s.currentSum += n;
}
}
Collections.sort(sums);
return calculate(copySums(sums), K, n, (int) chosenSum.currentSum);
}
public static List<Sum> copySums(List<Sum> sums) {
ArrayList<Sum> result = new ArrayList<>();
for (Sum s : sums) {
result.add(new Sum(s));
}
return result;
}
此代码 returns 30050 以防 100 57。 100 93 测试用例仍然 50778。
我是 Java 的新手。因此，我正在使用这种天真的方法来查找您的问题的结果。 我正在计算行总和和列总和并找到最小值并相应地将其递增 +1。 当我遇到行和列的相同值时，即当我尝试保留上一次迭代的行和列值并从那里获取下一个最小值并递增它时。
此外，我不仅处理了 NxN 矩阵，还处理了 MxN 矩阵。
下面是我解决这个问题的方法：
try {
for (k = 0; k < 4; k++) {
int rowSum[] = new int[arr.length];
int columnSum[] = new int[arr[0].length];
// Gets the sum for rows
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < ((arr[0].length)); j++) {
rowSum[i] = rowSum[i] + arr[i][j];
}
}
System.out.println("Row sum is: " + Arrays.toString(rowSum));
// Gets the sum for columns
for (int j = 0; j < arr[0].length; j++) {
for (int i = 0; i < (arr.length); i++) {
columnSum[j] = columnSum[j] + arr[i][j];
}
}
System.out.println("Column sum is: " + Arrays.toString(columnSum));
// to find the smallest
int minRowSumValue = rowSum[0];
for (int i = 0; i < rowSum.length; i++) {
if (rowSum[i] < minRowSumValue) {
minRowSumValue = rowSum[i];
}
}
System.out.println("Min row sum value is: " + minRowSumValue);
int minColSumValue = columnSum[0];
for (int i = 0; i < columnSum.length; i++) {
if (columnSum[i] < minColSumValue) {
minColSumValue = columnSum[i];
}
}
System.out.println("Min column sum value is: " + minColSumValue);
if (minRowSumValue < minColSumValue) {
int a = getArrayIndex(rowSum, minRowSumValue);
for (int i = a; i < arr.length; i++) {
for (int j = 0; j < ((arr[0].length)); j++) {
arr[i][j] = arr[i][j] + 1;
}
oldMinSumColValue = minColSumValue;
oldMinSumRowValue = 0;
finalSum += minRowSumValue;
break;
}
} else if (minColSumValue < minRowSumValue) {
int a = getArrayIndex(columnSum, minColSumValue);
for (int j = a; j < arr[0].length; j++) {
for (int i = 0; i < (arr.length); i++) {
arr[i][j] = arr[i][j] + 1;
}
oldMinSumRowValue = minRowSumValue;
oldMinSumColValue = 0;
finalSum += minColSumValue;
break;
}
} else if(minRowSumValue == minColSumValue) {
if (oldMinSumRowValue != 0) {
int a = getArrayIndex(rowSum, oldMinSumRowValue);
for (int i = a; i < arr.length; i++) {
for (int j = 0; j < ((arr[0].length)); j++) {
arr[i][j] = arr[i][j] + 1;
}
finalSum += minRowSumValue;
break;
}
} else {
int a = getArrayIndex(columnSum, oldMinSumColValue);
for (int j = a; j < arr[0].length; j++) {
for (int i = 0; i < (arr.length); i++) {
arr[i][j] = arr[i][j] + 1;
}
finalSum += minColSumValue;
break;
}
}
}
System.out.println("\nArray is: " + Arrays.deepToString(arr));
}
System.out.println("\n\nFinal Array after "+k+" steps is: " + Arrays.deepToString(arr));
System.out.println("\nFinal sum value is: "+finalSum);
} catch (Exception e) {
// TODO: handle exception
System.out.println("Exception is: " + e);
}
您可以通过使用更好的方法轻松提高效率。
下面是我的代码。当它遇到不明确的情况时（当在行和列中都可以找到最小值时），它会尝试两种情况并输出最小值。
对于每次迭代，它都会对两个 n 值列表进行排序。所以复杂度是 O(C*k*n log n)，其中 C 是不同路径的数量。我相信这非常接近最佳（就暴力的复杂性而言），因为在每次迭代之后，恰好 n+1 值会发生变化，因此我们至少需要触及它们中的每一个（当然，除非，一些更多的算法洞察力让我们只接触其中的几个）。根据 k 和 n 的值，这可能不够好，也可能不够好。对于案例 2，它运行的时间略多于 1 秒。
import java.util.Scanner;
import java.io.File;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;
/**
* 11 Aug 2016
* To answer the following question:
*
*/
class MinRowCol {
public static boolean DEBUG = false;
public static boolean USE_QUICK_ALGO = false;
public static boolean PREFER_ROW = true;
public static boolean USE_SUM_COUNT = false;
public static void inc(HashMap<Integer, Integer> sumCount, int key){
int oldVal = sumCount.getOrDefault(key, 0);
sumCount.put(key, oldVal+1);
}
public static void dec(HashMap<Integer, Integer> sumCount, int key){
int oldVal = sumCount.getOrDefault(key, 0);
sumCount.put(key, oldVal-1);
}
/**
* The class to store a sum
*/
private static final class Sum implements Comparable<Sum>{
public int sum;
public boolean isRow;
/** Count the number of each sum appearing as row sum (used in quick algo) */
public static HashMap<Integer, Integer> rowSumCount = new HashMap<Integer, Integer>();
/** Count the number of each sum appearing as col sum (used in quick algo) */
public static HashMap<Integer, Integer> colSumCount = new HashMap<Integer, Integer>();
public Sum(int sum, boolean isRow){
this.sum = sum;
this.isRow = isRow;
}
/**
* Returns how many times this sum appears in the matrix
* This function is used in quick algo
*/
public int getSumCount(){
int sumCount = 0;
if(this.isRow){
sumCount = rowSumCount.get(this.sum);
} else {
sumCount = colSumCount.get(this.sum);
}
return sumCount;
}
/**
* Update this sum with the diff
* This will properly update the sum count (this feature is for quick algo)
*/
public void update(int diff){
HashMap<Integer, Integer> sumCount;
if(this.isRow){
sumCount = rowSumCount;
} else {
sumCount = colSumCount;
}
dec(sumCount, this.sum);
inc(sumCount, this.sum+diff);
this.sum += diff;
}
/**
* Compare based on sum value
* In quick algo, if the value is the same, the one with higher multiplicity
* (i.e., appearing multiple times) has priority (i.e., smaller than the other)
*/
public int compareTo(Sum s){
if(this.sum < s.sum){
return -1;
} else if(this.sum > s.sum){
return 1;
} else {
if(USE_QUICK_ALGO){
if(USE_SUM_COUNT){
int result = -Integer.compare(this.getSumCount(), s.getSumCount());
if(result != 0){
return result;
}
}
if(PREFER_ROW){
return Boolean.compare(this.isRow, s.isRow);
} else {
return -Boolean.compare(this.isRow, s.isRow);
}
} else {
return 0;
}
}
}
public String toString(){
if(USE_QUICK_ALGO){
return String.format("%d %d %s", this.sum, this.getSumCount(), this.isRow ? "row" : "col");
} else {
return String.format("%d %s", this.sum, this.isRow ? "row" : "col");
}
}
}
public static void main(String[] args) throws Exception{
String inputFile = args[0];
if(args.length > 1){
for(int i=1; i<args.length; i++){
if(args[i].equals("-v")){
DEBUG = true;
} else if(args[i].equals("-quick")){
USE_QUICK_ALGO = true;
} else if(args[i].equals("-prefer_row")){
PREFER_ROW = true;
} else if(args[i].equals("-prefer_col")){
PREFER_ROW = false;
} else if(args[i].equals("-use_sum_count")){
USE_SUM_COUNT = true;
}
}
}
Scanner scanner = new Scanner(new File(inputFile));
String line = scanner.nextLine();
String[] tokens = line.split(" ");
int n = Integer.parseInt(tokens[0]);
int k = Integer.parseInt(tokens[1]);
int[][] matrix = new int[n][n];
Sum[] rowSums = new Sum[n];
Sum[] colSums = new Sum[n];
for(int i=0; i<n; i++){
rowSums[i] = new Sum(0, true);
colSums[i] = new Sum(0, false);
}
HashMap<Integer, Integer> rowSumCount = Sum.rowSumCount;
HashMap<Integer, Integer> colSumCount = Sum.colSumCount;
// Initialize the row sum and col sum
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
matrix[i][j] = scanner.nextInt();
rowSums[i].sum += matrix[i][j];
colSums[j].sum += matrix[i][j];
}
}
// Initialize the sum count (NOT USED)
for(int i=0; i<n; i++){
Sum rowSum = rowSums[i];
int val = rowSumCount.getOrDefault(rowSum.sum, 0);
rowSumCount.put(rowSum.sum, val+1);
Sum colSum = colSums[i];
val = colSumCount.getOrDefault(colSum.sum, 0);
colSumCount.put(colSum.sum, val+1);
}
int totSum = minSum(rowSums, colSums, 0, k, new String[k], 0);
System.out.println(totSum);
}
/**
* Returns the minimum sum after running the procedure for (maxIter-iter) iterations
* The arguments `selected` and `totSoFar` are for recording the path and the minimum sum, respectively
*/
public static int minSum(Sum[] rowSums, Sum[] colSums, int iter, int maxIter, String[] selected, int totSoFar){
int totSum = 0;
int n = rowSums.length;
// Consider the minimum in the row and the minimum in the column
// We don't need to consider multiple minimum values in a row/column
// since once a minimum value in a row gets picked, the next iteration
// will surely choose the minimum in the row, since the minimum in
// the column is no longer a minimum
Sum minRow = null;
Sum minCol = null;
for(int j=0; j<n; j++){
if(minRow == null || rowSums[j].sum < minRow.sum){
minRow = rowSums[j];
}
if(minCol == null || colSums[j].sum < minCol.sum){
minCol = colSums[j];
}
}
// Either try both row and column, or just pick row or pick column
Sum[] minSums;
if(minRow.compareTo(minCol) < 0){
minSums = new Sum[]{minRow};
} else if (minRow.compareTo(minCol) > 0){
minSums = new Sum[]{minCol};
} else {
minSums = new Sum[]{minRow, minCol};
}
int curMinSum = minSums[0].sum; // The minimum row/column sum in this iteration
int subSums = Integer.MAX_VALUE; // To hold the minimum sum after this iteration
for(Sum minSum: minSums){ // Try all (either one or two) choices
// Update the sums
if(minSum.isRow){
for(int j=0; j<n; j++){
colSums[j].update(1);
}
} else {
for(int j=0; j<n; j++){
rowSums[j].update(1);
}
}
selected[iter] = minSum.toString();
minSum.update(n);
if(iter < maxIter - 1){
int nextSubSums = minSum(rowSums, colSums, iter+1, maxIter, selected, totSoFar+curMinSum);
if(nextSubSums < subSums){
subSums = nextSubSums;
}
} else {
subSums = 0;
if(DEBUG){
System.out.print("End ("+(totSoFar+curMinSum)+"): ");
for(int i=0; i<selected.length; i++){
System.out.print(selected[i]+" ");
}
System.out.println();
}
}
// Revert the sum update we have done earlier
minSum.update(-n);
if(minSum.isRow){
for(int j=0; j<n; j++){
colSums[j].update(-1);
}
} else {
for(int j=0; j<n; j++){
rowSums[j].update(-1);
}
}
}
// Return minimum row/col found at this iter + the minimum sum in
// all iterations after this iteration
return curMinSum + subSums;
}
}
如果您提供 -v 参数，它也可以打印它选择的路径：
java MinRowCol MinRowCol.test -v
还有其他选项：
-quick - This will reduce the number of cases explored by using heuristics. The heuristics can be specified with other options
-prefer_col - This will prefer column over row (by default prefer row)
-use_sum_count - This will use the multiplicity of the sum
小测试用例如下：
3 2 1 0 1 0 1 1 0 0 1
它将输出：
End (3): 1 row 2 row End (3): 1 row 2 col End (2): 1 col 1 col 2
意味着它找到了三个可能的路径，其中两个的值为 3，一个的得分为 2。所以它选择了值为 2 的那个，你可以看到它做出的选择（总和和 row/col).您可以看到，首先选择列会导致最后的值变小。
案例三（案例二的选项太多，这里就不一一展示了）四个案例的答案是一样的：
End (50778): 455 1 col 480 1 col 486 1 row 494 1 col 498 1 row 500 1 col 502 1 col 506 1 col 509 1 col 510 1 col 512 2 row 512 1 row 513 1 row 514 1 row 515 1 row 519 2 row 519 1 row 520 1 row 524 1 row 525 1 col 526 1 col 527 1 col 529 1 row 530 1 row 531 1 row 533 1 row 534 2 row 534 1 row 535 2 row 535 1 row 538 2 row 538 1 row 539 2 row 539 1 row 541 3 row 541 2 row 541 1 row 542 1 row 543 2 row 543 1 row 544 2 row 544 1 row 545 1 row 548 1 row 549 3 row 549 2 row 549 1 row 550 1 row 553 3 row 553 2 row 553 1 row 554 2 row 554 1 row 556 1 row 557 2 row 557 1 row 558 1 row 559 3 row 559 2 row 559 1 row 561 1 row 563 2 row 563 1 row 564 4 row 564 3 row 564 2 row 564 1 row 565 1 row 567 2 row 567 1 row 569 1 row 570 2 row 570 1 row 571 1 row 572 1 row 573 1 row 574 3 row 574 2 row 574 1 row 575 2 row 575 1 row 576 2 row 576 1 row 577 2 row 577 1 row 578 2 row 578 1 row 579 1 row 582 1 row 583 2 row 583 1 row 584 2 row 584 1 row End (50778): 455 1 col 480 1 col 486 1 row 494 1 col 498 1 row 500 1 col 502 1 col 506 1 col 509 1 col 510 1 col 512 2 row 512 1 row 513 1 row 514 1 row 515 1 row 519 2 row 519 1 row 520 1 row 524 1 col 525 1 row 526 1 col 527 1 col 529 1 row 530 1 row 531 1 row 533 1 row 534 2 row 534 1 row 535 2 row 535 1 row 538 2 row 538 1 row 539 2 row 539 1 row 541 3 row 541 2 row 541 1 row 542 1 row 543 2 row 543 1 row 544 2 row 544 1 row 545 1 row 548 1 row 549 3 row 549 2 row 549 1 row 550 1 row 553 3 row 553 2 row 553 1 row 554 2 row 554 1 row 556 1 row 557 2 row 557 1 row 558 1 row 559 3 row 559 2 row 559 1 row 561 1 row 563 2 row 563 1 row 564 4 row 564 3 row 564 2 row 564 1 row 565 1 row 567 2 row 567 1 row 569 1 row 570 2 row 570 1 row 571 1 row 572 1 row 573 1 row 574 3 row 574 2 row 574 1 row 575 2 row 575 1 row 576 2 row 576 1 row 577 2 row 577 1 row 578 2 row 578 1 row 579 1 row 582 1 row 583 2 row 583 1 row 584 2 row 584 1 row End (50778): 455 1 col 480 1 col 486 1 row 494 1 col 498 1 row 500 1 col 502 1 col 506 1 col 509 1 col 510 1 col 512 2 row 512 1 row 513 1 row 514 1 row 515 1 row 519 2 row 519 1 row 520 1 row 524 1 col 525 1 col 526 1 row 527 1 col 529 1 row 530 1 row 531 1 row 533 1 row 534 2 row 534 1 row 535 2 row 535 1 row 538 2 row 538 1 row 539 2 row 539 1 row 541 3 row 541 2 row 541 1 row 542 1 row 543 2 row 543 1 row 544 2 row 544 1 row 545 1 row 548 1 row 549 3 row 549 2 row 549 1 row 550 1 row 553 3 row 553 2 row 553 1 row 554 2 row 554 1 row 556 1 row 557 2 row 557 1 row 558 1 row 559 3 row 559 2 row 559 1 row 561 1 row 563 2 row 563 1 row 564 4 row 564 3 row 564 2 row 564 1 row 565 1 row 567 2 row 567 1 row 569 1 row 570 2 row 570 1 row 571 1 row 572 1 row 573 1 row 574 3 row 574 2 row 574 1 row 575 2 row 575 1 row 576 2 row 576 1 row 577 2 row 577 1 row 578 2 row 578 1 row 579 1 row 582 1 row 583 2 row 583 1 row 584 2 row 584 1 row End (50778): 455 1 col 480 1 col 486 1 row 494 1 col 498 1 row 500 1 col 502 1 col 506 1 col 509 1 col 510 1 col 512 2 row 512 1 row 513 1 row 514 1 row 515 1 row 519 2 row 519 1 row 520 1 row 524 1 col 525 1 col 526 1 col 527 1 row 529 1 row 530 1 row 531 1 row 533 1 row 534 2 row 534 1 row 535 2 row 535 1 row 538 2 row 538 1 row 539 2 row 539 1 row 541 3 row 541 2 row 541 1 row 542 1 row 543 2 row 543 1 row 544 2 row 544 1 row 545 1 row 548 1 row 549 3 row 549 2 row 549 1 row 550 1 row 553 3 row 553 2 row 553 1 row 554 2 row 554 1 row 556 1 row 557 2 row 557 1 row 558 1 row 559 3 row 559 2 row 559 1 row 561 1 row 563 2 row 563 1 row 564 4 row 564 3 row 564 2 row 564 1 row 565 1 row 567 2 row 567 1 row 569 1 row 570 2 row 570 1 row 571 1 row 572 1 row 573 1 row 574 3 row 574 2 row 574 1 row 575 2 row 575 1 row 576 2 row 576 1 row 577 2 row 577 1 row 578 2 row 578 1 row 579 1 row 582 1 row 583 2 row 583 1 row 584 2 row 584 1 row 50778
对于情况2，结果如下：
没有选项（搜索所有案例）：
30050
使用-quick -prefer_row:
30066
使用-quick -prefer_col:
30050
所以我们确实需要探索多条路径。但我不确定为什么情况 3 的正确答案应该是 50708 而不是 50778。
您实际上不需要保留整个矩阵，只需要按行和按列的总和。
给定一个 NxN 矩阵，令 SumByRow 为长度为 N 的向量，其中包含矩阵每一行的总和，令 SumByCol 与列相同。在您的示例中，这些向量将是：
Matrix = [ [1,3],
[2,4]]
SumByRow = [4,6]
SumByCol = [3,7]
现在，无论最小行[列]的实际索引如何，我们都可以确定一件事：在下一次迭代中，SumByRow[Col] 向量的一个元素将递增 N（因为我们正在添加一个到该行 [列] 的每个元素）并且 SumByCol [行] 将向其每个元素添加 1（因为无论总和是什么，我们将一对一且仅将组成它的元素之一相加）。
所以我们可以摆脱丑陋的大矩阵并使用这两个向量。 上面的推理也提出了一种实现迭代的方法，即：
Step one: find index of minimum element between both vectors
Step two: increase final sum by that element's value, increase that element by N, increase each element of other vector by one
Step three: rinse and repeat until smooth anf fluf- enough iterations have been calculated
最后一个问题，行列求和的最小值相同怎么办？ 随机并没有真正的帮助，也不是总是选择一个而不是另一个，因为这些方法可能会让你进入一个次优的车道，然后需要某种形式的前瞻性。 我选择了一个简单的模拟，如果两个选项都无效，下一步会发生什么，以递归但有限的方式，以便尽可能多地尝试和展望未来。 但是可能会有更有效的启发式方法，甚至是完全完整的策略，但 none 现在我想到了。
编辑： 实际上，多亏了 justhalf，我不再确定局部贪婪方法有什么好处，因为最优策略可能从一些不是明确最优的选择开始...
这是我拼凑来演示的代码，它很丑陋，但我希望可以理解，如果您发现错误或需要任何说明，请告诉我 https://ideone.com/EZW3wt
from numpy import matrix
import numpy as np
n = 2
k = 4
A = matrix([[1,3],
[2,4]
])
sc = [0]*n
sr = [0]*n
for i in range(0,n):
sc[i] = sum( A.A[:,i] )
sr[i] = sum( A.A[i,:] )
output=0
def whichmin(c,r, iter):
if(iter < 0):
return 1
r[np.argmin(r)] += n
c[np.argmin(c)] += n
if ( np.amin(c) < np.amin(r) ):
return 1
elif ( np.amin(r) < np.amin(c) ):
return 0
else :
return whichmin(c,r, (iter -1) )
for j in range(0,k):
minc = np.amin(sc)
minr = np.amin(sr)
if (minc < minr):
incrindex = np.argmin(sc)
sc[incrindex]+=n
sr = [x+1 for x in sr]
output += minc
elif (minr < minc):
incrindex = np.argmin(sr)
sr[incrindex]+=n
sc = [x+1 for x in sc]
output += minr
else :
min = whichmin(sc.copy(),sr.copy(), (n - i) )
if (min==1):
incrindex = np.argmin(sc)
sc[incrindex]+=n
sr = [x+1 for x in sr]
output += minc
else:
incrindex = np.argmin(sr)
sr[incrindex]+=n
sc = [x+1 for x in sc]
output += minr
print(output)
print(sc)
print(sr)