java矩阵中x长度的任意路径中最大值和最小值之间的最小差

Question

我有一个{a1}任务，我正在努力完成。 任务是“在矩阵中找到一组至少有k个连通项的集合，这样集合中最大项和最小项之间的差异就最小化了”

首先输入矩阵的大小：

5 10

然后，矩阵的值：

0  0  3  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();
  }

但不知道如何遍历矩阵，获得所有不同的路径，或找到他们要求的值。我已经在谷歌上搜索动态规划和其他东西好几天了，没有任何结果

提前感谢您的帮助

Answer 1

{}中的第一个算法：

考虑到矩阵的小规模，您可能会选择一种非常简单的方法，在时间O((RC)^3)中运行，即：

1. 将所有高度值alts存储在单独的数组中并对其进行排序

现在，对于此数组alts的所有值对(L,H)，L <= H：

1. 考虑矩阵B，使得b(i,j) = 1如果L <= a(i,j) <= H，则b(i,j) = 0否则
2. 使用几个BFS或联合查找结构来查找B中最大的1值连通分量的大小

现在您知道了每对(L,H)，k(L,H)，值的最大连接分量的大小在L和H之间。现在，要找到给定k的最低高度差，只需计算所有对(L,H)的H-L最小值，这样k(L,H) >= k

每个请求中O((RC)^2 log(RC))的变化：

对于任何给定的k，对于L（最低点）的所有可能值，对H（最高点的值）进行二分法搜索，以找到最低的H，从而k(L,H) >= k。这是可能的，因为H1 >= H2意味着所有L的k(L,H1) >= k(L,H2)

最后，在O((RC)^2 log(RC))中的解决方案

对于矩阵中的所有点，开始Dijkstra搜索（优先级是海拔高度，您永远不会去高于起始海拔的点）。每次搜索背后的假设是，你从山顶开始搜索，然后只从那里往下走，慢慢增加高差

与前面一样，在这个计算过程中，您会得到给定(L,H)的连接组件，其中的大小k(L,H)。这允许您计算实现所有{}的给定{}的最低差值{}，从而回答所有问题（您可以在一个{}大小的数组中存储{}到{}的{}的所有最小{}）

Answer 2

我也许能帮你开始。解决这些问题的一个好方法是首先提出一个简单的解决方案，然后进行优化。解决此问题的简单方法可能如下所示：

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;
}

该算法在图形中的每个节点上循环，构建与该节点的最小距离区域，查看这些节点之间的最大距离当前是否全局最优，如果是，则存储最大距离。您可以获取这个伪代码，键入它，然后对其进行优化。我希望这对你来说已经足够了。这个算法没有经过优化