我不擅长以编程方式实现上面提到的启发式搜索算法/Dijkstra 算法/A* 搜索算法。然而，在解决我的一篇帖子 ( Matrix manipulation: logic not fetching correct answer for higher order NXN matrix data ) 中提到的问题时，我发现我解决问题的方法存在缺陷。问题陈述如下。
问题陈述
有一个NxN矩阵，分为N * N个单元格。每个单元格都有一个预定义的值。这将作为输入给出。迭代必须发生 K 次，这也在测试输入中给出。我们必须确保在每次迭代中选择行/列的最佳/最小值。最终输出为每次迭代结束时保存的最优值的累加和。
步骤 1. 对单个行和列求和，求行和列的最小和，(可以是行也可以是列，只需要最小的行或列即可)
Step 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 大小矩阵的测试用例时，许多测试用例都失败了。最初，我认为这是数组大小增加时出现的一些内存问题/堆栈溢出，但现在我发现这是代码中的一个缺陷，我无法预测最终会引导我找到最佳解决方案的正确路径我想实现。
我在我的代码中发现的缺陷是，在一种情况下，行和列的最佳值相等。我可以自由选择行或列，但是，这里的问题是，如果我先选择行，它可能会将行的值更新为某个非最佳值，我相信只有我事先知道所有最佳路径会帮助我得到正确的答案。
在这方面的任何帮助将不胜感激。
此问题引用了此处提出的问题。 Matrix manipulation: logic not fetching correct answer for higher order NXN matrix data
只有在使用高阶矩阵时，我才能在应用上述方法时得到以下输出差异。 编辑:
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;
}
此代码在 100 57 的情况下返回 30050。对于 100 93 测试用例，仍然是 50778。
关于java - 如何遍历所有可能的解决方案路径并选择最佳路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38697500/