如何从起点找到二维数组中相邻元素的最大和

Question

有一个 4x4 二维数组，例如，（每个元素的范围在 0 到 9 之间）

4512
3712
1345
3312

我试图从一个点中找到最多 4 个相邻元素。（不包括对角线）

例如，如果选择点 (1,2) 作为起点，可以从 (1,2) 移动 (1,1) 或 (2,2) 或 (1,3) 相邻元素。如果下一个选择（2,2），则可以移动（2,1）或（3,2）或（2,3）。依此类推，直到选择 4 个元素。

如果您选择 4 个元素，例如， (1,2)->(2,2)->(2,1)->(1,1) 总和是 3 + 7 + 5 + 4 = 19

我正在尝试使用 dfs 或 bfs 寻找可能的候选人。

但是，它不能为候选人做出上述，(1,1) -> (1,2) -> (2,1) -> (2,2)

这个问题有什么解决办法吗？

Answer 1

还没有完整的答案

使用动态规划。

在总和数组中，位置 (i,j) 的值包含使用 (i,j) 元素和仅向右或向下方向的元素可能的最大总和。

缺少链：不会考虑像 (0,0)、(0,1)、(1,1) 和 (1,0) 这样的元素链

var array = [
  [4, 5, 1, 2],
  [3, 7, 1, 2],
  [1, 3, 4, 5],
  [3, 3, 1, 2],
]

var sum1 = array;

var sum2 = getNextOrderSum(sum1, array);
var sum3 = getNextOrderSum(sum2, array);
var sum4 = getNextOrderSum(sum3, array);

print(sum4);

// Given max sum array of n adjacent elements and original array
// Return max sum array of n+1 adjacent elements
function getNextOrderSum(input, array) {
  var sum = [];
  for (var i = 0; i < input.length; i++) {
    sum[i] = [];
    for (var j = 0; j < input[0].length; j++) {
      sum[i][j] = array[i][j] + Math.max(get(input, i, j + 1), get(input, i + 1, j));
    }
  }

  return sum;
}

// Utility method to get i,j element of array with boundary checks
function get(array, i, j) {
  if (i < 0 || j < 0)
    return 0;
  if (i >= array.length)
    return 0;
  if (j >= array[0].length)
    return 0;

  return array[i][j];
}

// Utility method for printing
function print(array) {
  var s = "";
  for (var i = 0; i < array.length; i++) {
    s += array[i].toString() + "\n"
  }
  console.log(s);
}

Answer 2

使用 3D 数组 dp[n][m][4]

其中 n 和 m 是数组的维度

和4用于告诉元素在链中的位置。

基本情况- 我们将元素 (i,j) 的值存储在 dp[i][j][k] if k=3 中，或者当元素是链中的最后一个时 or if i and j 是 数组的边界 （普通情况）。

DP公式- 让用于执行任务的函数为 dpFUNCTION()

dp[i][j][k]=array[i][j] + mAX( dpFUNCTION(i+1,j,k+1), dpFUNCTION(i,j+1,k+1), dpFUNCTION(i-1,j,k+1), dpFUNCTION(i,j-1,k+1));

编辑- 让我们从简单的案例开始并将其扩展到您的问题。实际上你可以用这种方式做大多数 DP 题，即分解成简单的形式并扩展它。

1) 现在，如果我们只需要找到数组中一个数字的相邻数字的最大值，我们可以简单地用 -

填充 dp1[i][j]

dp1[i][j]=max(array[i-1][j], array[i+1][j], array[i][j+1], array[i][j-1]);
//max of adjacent numbers

2) 现在，如果我们必须找到 2 个相邻数字的最大值，我们可以使用我们的 dp1[][] 数组，如下所示-

dp2[i][j]= max(array[i-1][j]+dp1[i-1][j], array[i-1][j]+dp1[i-1][j], array[i-1][j]+dp1[i-1][j], array[i-1][j]+dp1[i-1][j]);

对于长度为2的链，我们需要得到它的相邻数字的总和（比如array[i-1][j]）和它的相邻数字的最大值（计算存储在dp[i-1][j]中).然后我们将所有相邻数字的最大值存储在 dp2.

3)同样，如果链的长度为3，我们使用dp2[][]如下-

dp3[i][j]= max(array[i-1][j]+dp2[i-1][j], array[i-1][j]+dp2[i-1][j], array[i-1][j]+dp2[i-1][j], array[i-1][j]+dp2[i-1][j]);

4)最后，对于长度为4的链，我们得到-

dp4[i][j]= max(array[i-1][j]+dp3[i-1][j], array[i-1][j]+dp3[i-1][j], array[i-1][j]+dp3[i-1][j], array[i-1][j]+dp3[i-1][j]);

这是必需的解决方案，我所做的是将所有这 4 个数组组合成 dp[n][m][4] 并以 混乱的方式 填充它，而不是按步骤进行解释。即使包含对角线，您也可以使用相同的方法。

Answer 3

一种可能的方法是创建具有所有旋转和反射的 5 tetrominoes（抱歉，不能 post 图像）的预定义常量（当然您不需要旋转 'square' 或反映对称的）。然后你可以获取这些常量中的每一个并将你的起点映射到所选常量的每个点。

另一种方法是通过算法枚举四联骨牌。 wikipedia 中描述了一些算法。

如何从起点找到二维数组中相邻元素的最大和

how to find max sum of adjacent elements in 2d array from a starting point

algorithm

dynamic-programming

graph-algorithm

path-finding

greedy

还没有完整的答案