NodeJS 基于矩阵的国际象棋/车问题的平方是最大计数

8e2ybdfx 于 2023-10-17 发布在 Node.js

关注(0)|答案(2)|浏览(111)

给你一个矩阵A，代表一个有N行M列的棋盘。棋盘的每一个方格都包含一个整数，代表一个基于点数的分数。你必须把两辆车放在棋盘上，这样它们就不能互相攻击，而且它们的方格上的点数之和是最大的。国际象棋中的车只有在同一行或同一列时才能互相攻击。
例如，给定下图中的矩阵：

我们可以用两种不同的方式来放置车

一辆车在A[00][00] = 1，另一辆车在A[01][02] = 3。这些正方形上的点数之和是4。
一辆车在A[00][02] = 4，另一辆车在A[01][00] = 2。这些正方形上的点数之和是6。你的任务是找到两个可以放置车的棋盘格的最大和。在上面的例子中，答案是6。例如，我们不能把车放在A[00][02]和A[01][02]（它们的和是7），因为它们会互相攻击。

写一个函数：函数解（A）;给定矩阵A，返回放置两个非攻击车所能达到的最大和

示例：

1.给定两行两列的矩阵A：

函数返回6。我们可以通过选择A[00][02] + A[01][00] = 4 + 2来实现最大和。选定的方块以绿色标记
1.给定一个三行三列的矩阵A：

函数返回23。我们可以通过选择A[00][00] + A[01][02] = 15 + 8来实现最大和。选定的方块以绿色标记。
1.给定三行两列的矩阵A：

该函数将返回24。我们可以通过选择A[00][00] + A[01][02] = 12 + 12或A[00][02] + A[01][00] = 12 + 12来实现最大和。后者溶液用绿色标记。
1.给定两行三列的矩阵A：

该函数将返回22。我们可以通过选择A[00][02] + A[01][00] = 14 + 8来实现最大和。选定的方块以绿色标记。为下列假设编写一个有效的算法
N和M是在**[2..600]范围内的整数;矩阵A的每个元素是范围[0..1，000，000，000]**内的整数。
我试过了，但不认为这是有效的。

function solution(A) {
    const N = A.length;
    const M = A[0].length;
    let maxSum = 0;

    if(N > M){
        for (let i = 0; i < N; i++) {
            for (let j = i + 1; j < N; j++) {
                for (let col1 = 0; col1 < M; col1++) {
                    for (let col2 = col1 + 1; col2 < M; col2++) {
                        if (col1 !== col2) {
                            const sum = A[i][col1] + A[j][col2];
                            maxSum = Math.max(maxSum, sum);
                        }
                    }
                }
            }
        }
        return maxSum;
    }

    for (let i = 0; i < N; i++) {
        for (let j = i + 1; j < N; j++) {
            for (let col1 = 0; col1 < M; col1++) {
                for (let col2 = 0; col2 < M; col2++) {
                    if (col1 !== col2 && A[i][col1] !== A[j][col2]) {
                        maxSum = Math.max(maxSum, A[i][col1] + A[j][col2]);
                    }
                }
            }
        }
    }
    return maxSum;
}

node.js

来源：https://stackoverflow.com/questions/77293633/matrix-based-chess-rook-question-on-square-to-be-maximum-count

2条答案

按热度按时间

yks3o0rb1#

你可以在线性时间内解决这个问题。
只需逐行遍历矩阵，然后：

当您完成每一行时，请跟踪到目前为止在较高行的每一列中看到的最大值。
从左到右遍历每一行，使用这些列值跟踪最大值的上方和左侧，并将其添加到当前值。这将找到所有像这样的车排列的和\。
从右到左遍历每一行，找到像/这样的车排列。

function solution(A) {
    // TODO make sure dimensions are >= 2x2
    let maxSum = A[0][0] + A[1][1];

    // track the maximum in each column
    const colMax = [...(A[0])];

    for (let r = 1;r < A.length; r++) {
        const row = A[r];
        // find \ orientations
        let rectMax = colMax[0];
        for (let c = 1; c<row.length; ++c) {
            maxSum = Math.max(maxSum, row[c]+rectMax);
            rectMax = Math.max(rectMax, colMax[c]);
        }
        // find / orientations
        rectMax = colMax[row.length-1];
        for (let c=row.length-2; c>=0; --c) {
            maxSum = Math.max(maxSum, row[c]+rectMax);
            rectMax = Math.max(rectMax, colMax[c]);
        }
        // update colmax
        for (let c=0; c<row.length; ++c) {
            colMax[c] = Math.max(colMax[c], row[c]);
        }
    }
    return maxSum;
}

赞(0）回复(0）举报 2023-10-17

1dkrff032#

我们可以很容易地在一个函数的基础上构建这个函数，该函数创建一个网格，删除与给定正方形共享一行或一列的所有单元格。该函数反过来可以写在从数组中删除给定索引的函数之上。它可能看起来像这样：

// Removes an index from an array; returns a copy, not mutating
const without = (i) => (xs) => [...xs.slice(0, i), ...xs.slice(i + 1)]

// Removes a row and column from a rectangular grid; returns a copy, not mutating
const removeSquare = (r, c) => (ss) => without(r)(ss).map(without(c))

// Finds the maximum sum of square values for two non-attacking rooks
const maxRookSum = (board) =>
  board.length <= 1 || board[0].length <= 1
    ? -Infinity
    : Math.max(
        maxRookSum(board.slice(1)),
        Math.max(...board[0].map((v, i) => v + Math.max(...removeSquare(0, i)(board).flat()))),
      )

console.log(maxRookSum([
  [1, 4,],
  [2, 3,],
])) //=> 2 + 4 => 6

console.log(maxRookSum([
  [15, 1, 5,],
  [16, 3, 8,],
  [2,  6, 4,],
])) //=> 15 + 8 => 23

console.log(maxRookSum([
  [12, 12,],
  [12, 12,],
  [ 0,  7,],
])) //=> 12 + 12 => 24

console.log(maxRookSum([
  [1, 2, 14,],
  [3, 8, 15,]
])) //=> 14 + 8 => 22

.as-console-wrapper {max-height: 100% !important; top: 0}

我们的主函数首先确保我们甚至可以得到两个非攻击车，这意味着我们至少有两行至少两列。如果不是，我们返回-Infinity作为信号。否则，我们会找到两个值的最大值：首先，我们跳过初始行，并在剩余的行上重复。其次，我们在第一行中测试每个值，删除相关的行和列，并找到最大的剩余正方形并将其添加到我们的单元格值中。这两个值的最大值是我们能做的最好的。
请注意，这种技术可以很容易地扩展到找到网格中 * 所有 * 非攻击车的最大总和，只需循环而不是扁平化并在第二个主分支中取最大值。（我知道，因为这是我第一次写关于误读问题的文章;这里介绍的版本只是稍微简单一点）。

赞(0）回复(0）举报 2023-10-17

我来回答

NodeJS 基于矩阵的国际象棋/车问题的平方是最大计数

2条答案

相关问题

热门标签

最新问答