我有一个卡蒂斯任务，我正在努力完成。 任务是"在矩阵中找到一组至少k个连接的条目，以便最小化集合中最大和最小条目之间的差异"。
输入首先是矩阵的大小：
5 10
然后是矩阵的值：
0 03 46 0 46 0 0 12 12 0 0 13 50 49 46 11 10 10 11 0 51 51 49 99 99 89 0 0 10 0 0 48 82 70 99 0 52 13 14 51 50 50 51 70 35 70 10 14 11
之后是 k 值的叠加：
6
然后是 k 上的实际值：
1 5 10 12 47 50
任务指出："矩阵中的条目a(i，j)与条目a(i，j+1)、a(i+1，j)、a(i，j-1)和a(i-1，j)相邻。如果对于集合中的每对条目，其中都有相邻条目的连接路径，则连接一组条目。
对于给定的值，输出应为：
0 0 3 4 89 99
我已经编写了代码来接受所有输入：
Scanner sc = new Scanner(System.in);
int r = sc.nextInt();
int c = sc.nextInt();
// fill with values
int[][] dimMat = new int[r][c];
for (int i = 0; i < dimMat.length; i++) {
for (int j = 0; j < dimMat[i].length; j++) {
dimMat[i][j] = sc.nextInt();
}
}
int n = sc.nextInt();
int[] myK = new int[n];
// fill k
for(int k= 0; k< myK.length; k++){
myK[k] = sc.nextInt();
}
但是不知道如何遍历矩阵，获取所有不同的路径或找到它们要求的值。几天来我一直在谷歌上搜索动态编程和其他东西，但没有任何结果。
提前感谢任何帮助。
我也许能让你开始。解决这些问题的一个好方法是首先提出一个幼稚的解决方案，然后进行优化。解决此问题的天真方法可能如下所示：
k = desired size of region;
minValue = infinity;
for every node in your graph {
S = an empty set of nodes;
add current node to s;
while(S.size < k) {
nextNode = infinity;
for every node in S called s {
N = the smallest connected node to s;
if N < nextNode
nextNode = n;
}
add nextNode to S;
}
find greatest difference between nodes in your set;
if greatestDifference < minValue
minValue = greatestDifference;
}
此算法遍历图形中的每个节点，构建与该节点距离最小的区域，查看这些节点之间的最大距离当前是否全局最佳，如果是，则存储最大距离。你可以获取这个伪代码，输入它，然后优化它。我希望这对你来说是一个足够的开始。这个算法是相当未经优化的。
O((RC)^3)中的第一个算法：
考虑到矩阵的尺寸很小，你也许可以采用一种非常幼稚的方法，在时间O((RC)^3)中运行，即：
- 将所有海拔
alts值存储在一个单独的数组中并对其进行排序
现在对于这个数组的所有对(L,H)，L <= H，alts：
- 考虑矩阵
B，如果L <= a(i,j) <= H，b(i,j) = 1，b(i,j) = 0否则。 - 使用多个
BFS或联合查找结构来查找 B 中最大的 1 值连接组件的大小。
您现在知道对于每对(L,H)，k(L,H)，L和H之间值的最大连通分量的大小。现在，要找到给定k的最低高度差，您只需计算所有对的最小H-L(L,H)，以便k(L,H) >= k。
每个请求的O((RC)^2 log(RC))变化：
对于任何给定k，对于L的所有可能值(最低点)，对H(最高点的值)进行二分搜索以找到最低H，以便k(L,H) >= k。这是可能的，因为H1 >= H2意味着对所有Lk(L,H1) >= k(L,H2)。
最后，O((RC)^2 log(RC))的解决方案
对于矩阵的所有点，开始 Dijkstra 搜索(优先级是高度，并且您永远不会转到高于起始高度的点)。每次搜索背后的假设是，您从山顶开始搜索，然后才从那里向下搜索，慢慢增加高度差。
和以前一样，在此计算过程中，您将获得给定(L,H)的连接组件，您知道其大小k(L,H)。这允许您计算为所有k实现给定k的最低差分H-L，从而回答所有问题(您可以将所有最小H-L存储在(RC+1)大小的数组中，以便从0到RCk)。