时间戳

首页 > 解决方案 > 在矩阵中找到 4 个方向上的最高乘积

php - 在矩阵中找到 4 个方向上的最高乘积

问题描述

我得到了这个挑战，要在 . 上找到 4 个连续数字的最高乘积20x20 matrix of integers。

这些数字是从由空格分隔的文件中逐行读取的。

产品可以水平、垂直和对角两个方向

我的“解决方案”给出了错误的答案。

编辑：我已经更新了代码以在没有文件输入的情况下工作并添加了示例数据；还修复了我在评论中指出的错误之一

$data = [
    [89,32,92,64,81,2,20,33,44,1,70,75,39,62,76,35,16,77,22,27],
    [53,11,6,95,41,51,31,59,8,23,19,13,61,91,48,69,84,52,66,24],
    [93,72,85,97,21,79,56,5,45,3,65,30,83,87,43,7,34,0,4,14],
    [29,17,49,9,82,90,55,67,15,63,54,94,12,28,96,37,58,98,86,78],
    [74,40,50,60,26,99,80,18,10,46,36,68,25,57,47,71,42,73,88,38],
    [50,22,6,26,18,53,52,5,46,2,89,77,83,48,4,58,45,28,84,81],
    [49,82,31,14,69,17,91,54,34,40,0,33,30,95,60,44,29,24,85,16],
    [27,11,76,39,15,86,92,74,99,59,94,12,55,57,38,96,47,32,78,75],
    [51,20,87,42,62,41,7,35,23,21,71,25,67,97,80,90,88,64,13,70],
    [19,9,56,43,68,93,65,98,36,3,61,63,10,72,8,73,1,66,79,37],
    [22,58,52,12,3,41,28,72,42,74,76,64,59,35,85,78,14,27,53,88],
    [46,80,5,96,7,68,61,69,67,34,36,40,82,26,75,50,29,91,10,2],
    [30,39,19,48,33,93,1,45,66,98,0,23,62,25,51,71,56,77,24,21],
    [79,87,94,60,8,32,13,65,4,92,73,9,31,37,17,84,15,90,86,20],
    [95,6,81,70,47,16,44,83,49,43,55,54,18,63,38,11,97,89,99,57],
    [95,78,64,58,7,17,53,28,74,86,6,12,54,85,21,94,16,69,25,68],
    [13,20,41,97,1,2,80,30,0,84,67,45,93,96,82,92,62,33,18,44],
    [60,77,31,70,76,36,59,38,15,3,91,46,65,73,49,11,8,35,5,52],
    [61,66,79,40,26,72,89,71,75,99,22,9,43,32,14,81,98,88,87,83],
    [10,4,23,19,56,57,51,47,50,27,90,63,42,29,24,55,48,37,39,34]
];

$matrix = [];
//maximums in possible directions
$maxes  = [0, 0, 0, 0];

//while ($line = trim(fgets(STDIN))) { 
while ($line = current($data)) {
    //the horizontal maxes can be calculated while loading
    //$array = explode(" ", $line);
    $array = $line;

    $hMax = array_product(array_slice($array, 0, 4));

    for ($i = 1; $i < (count($array)-4); $i++) {
        $max = array_product(array_slice($array, $i, 4));

        if($max > $hMax) {
            $hMax = $max;
        }
    }

    if ( $hMax > $maxes[0] ) {
        $maxes[0] = $hMax;
    }

    $matrix[] = $array;
    next($data);
}

// the last 3 rows can be skipped
for($i = 0; $i < (count($matrix)-4); $i++) {
    for ($j = 0; $j < (count($matrix[$i])-1); $j++) {

        $vMax  = 1;   // vertical
        $dlMax = 1;   // diagonal left
        $drMax = 1;   // diagonal rigth

        for ($k = 0; $k < 5; $k++) {
            $vMax  *= $matrix[$i + $k][$j];

            if ( $j < (count($matrix[$i]) - 4) ) {
                $drMax *= $matrix[$i + $k][$j + $k];
            }

            if ( $j > 3 ) {
                $dlMax *= $matrix[$i + $k][$j - $k];
            }
        }

        if ( $maxes[1] < $vMax )  $maxes[1] = $vMax;  // the index used to be 1 - my first mistake
        if ( $maxes[2] < $dlMax ) $maxes[2] = $dlMax; // the index used to be 1 - my first mistake
        if ( $maxes[3] < $drMax ) $maxes[3] = $drMax; // the index used to be 1 - my first mistake
    }
}

sort($maxes);
echo end($maxes).PHP_EOL;

我的方法哪里出了问题，如何加快速度？有没有可以在这里应用的数学技巧(besides checking for zeros)?

编辑：代码为当前数据提供的解决方案4912231320是否正确？

标签： phpalgorithmmatrix

解决方案

我们可以考虑四个方向，最底部或最右侧的单元格可以是序列中的最后一个。如果是来自 directionm[i][j][k][d]的长度序列的最高总和，则：kd

m[i][j][1][d] = data[i][j] for all d

m[i][j][k]['E'] = data[i][j] * m[i][j - 1][k - 1]['E']
m[i][j][k]['NE'] = data[i][j] * m[i - 1][j - 1][k - 1]['NE']
m[i][j][k]['N'] = data[i][j] * m[i - 1][j][k - 1]['N']
m[i][j][k]['NW'] = data[i][j] * m[i - 1][j + 1][k - 1]['NW']

如果我们从北到南、从东到西遍历，则应该已经计算出所需的单元格，而且，显然，我们正在寻找

max(m[i][j][4][d])
  for all i, j, d

推荐阅读