Найти кратчайший путь в квадратной матрице из [0,0] в [k1,k2]

Question

Найти кратчайший путь матрицы,из [0,0] в [k1,k2] где k1 показывает номер строки где находится максимальное число главной диагонали.k2 показывает номер столбца где находится максимальное число вспомогательной диагонали.

Код не работает правильно 4x4 матрице,поможете исправить?

function solution(x){
    var k1 = 0,k2 = 0,max1 = 0,max2 = 0
    if (x.toString().split(",").reduce((a,b)=>+a + +b)==0) {return 0}
    for (var i = 0; i < x.length; i++) {
        if (x[i].length<3) {return 0}
    }
    for (var i = 0; i < x.length; i++) {
        for (var j = 0; j < x.length; j++) {
            if (i==j) {
                if (max1<x[i][j]) {
                    max1 = x[i][j]
                    k1 = i
                }
            }
            if (i+j==x.length-1) {
                if (max2<x[i][j]) {
                    max2 = x[i][j]
                    k2 = j
                }
            }
        }
    }
    var s = x[0][0]
    for (var i = k1; i > -1; i--) {
        for (var j = k2; j > -1; j--) {
            if (x[i-1][j]>=x[i][j-1]) {
                s+=x[i][j-1]
                j--
            } else {
                s+=x[i-1][j]
                i--
            }
            if ((i-1==0 && j==0) || (i==0 && j-1==0) || i<=0 || j<=0) {
                return s
            }
        }
    }
}
console.log(solution([[1,4,3],[2,8,2],[1,5,3]])) //3
console.log(solution([[1,9,1],[4,0,9],[0,7,9]])) //12
console.log(solution([[1,9,9],[4,1,9],[12,7,9]])) //5
console.log(solution([[0,0,0],[0,0,0],[0,0,0]])) //0
console.log(solution([[0,0,0],[0,0,0],[0,1]])) //0
console.log(solution([[5],[1],[2]])) //0
console.log(solution([[1,2,3,4],[4,5,8,1],[2,4,5,10],[5,1,2,3]])) //6
console.log(solution([[1,2,3,4],[4,5,3,1],[2,4,5,10],[5,1,2,8]])) //8

Answer 1

Ваш алгоритм не вычисляет возможные пути к [k1, k2], а только находит кратчайший путь с минимальной суммой. Вы должны также проверять и остальные пути т.к. не всегда самый короткий путь будет иметь самую минимальную сумму.
Вы проверяете только движение от [k1, k2] до [0, 0] только в влево и вверх по матрице:

if (x[i-1][j]>=x[i][j-1]) {
    s+=x[i][j-1];
    j--;
} else {
    s+=x[i-1][j];
    i--;
}

а нужно также проверять движение вправо и вниз.

Вот пример рекурсивного алгоритма который подходит для ваших тестов, но не решает задачу в целом, поскольку также реализует только два направления движения по матрице (вниз и вправо).

var solutions = [];
var k1 = 2, k2 = 2;
var size = 3;

function solve(x, y, path, sum, m) {
    if (x == k1 && y == k2) {solutions.push(sum);}
    if (x + 1 < size) {
        let path_clone = path.map(function(arr) {return arr.slice();});
        path_clone.push([x+1, y]);
        solve(x+1, y, path_clone, sum + m[x][y], m);
    }
    if (y + 1 < size) {
        let path_clone = path.map(function(arr) {return arr.slice();});
        path_clone.push([x, y+1]);
        solve(x, y+1, path_clone, sum + m[x][y], m);
    }
}

function solution(m){
    size = m.length;
    d1 = [], d2 = [];
    for (let i = 0; i < size; i++) {
       d1.push(m[i][i]);
       d2.push(m[size-i-1][i]);  
    }
    k1 = d1.indexOf(Math.max(...d1));
    k2 = d2.indexOf(Math.max(...d2));
    solutions = [];
    solve(0, 0, [[0,0]], 0, m);
    return Math.min(...solutions);
}

console.log(solution([[1,4,3],[2,8,2],[1,5,3]])); //3
console.log(solution([[1,9,1],[4,0,9],[0,7,9]]));//12
console.log(solution([[1,9,9],[4,1,9],[12,7,9]])); //5
console.log(solution([[0,0,0],[0,0,0],[0,0,0]])); //0
console.log(solution([[1,2,3,4],[4,5,8,1],[2,4,5,10],[5,1,2,3]])); //6
console.log(solution([[1,2,3,4],[4,5,3,1],[2,4,5,10],[5,1,2,8]])); //7

БЛОГ НА HUSL

Найти кратчайший путь в квадратной матрице из [0,0] в [k1,k2]

Ответы (1 шт):