2

Есть матрица NxN с числами от 1 до N в случайном порядке, например, такая:

6   4   5
9   8   3
1   2   7

Как найти все возможные последовательности по вертикали и горизонтали, дающие в сумме M? Например, для 15 для данной матрицы дадут последовательности

6->4->5 
6->9
5->3->7
1->2->8->4
4->8->3

При этом каждый элемент может участвовать в неограниченном количестве последовательностей, но в одной повторяться не может.

Написать алгоритм, находящий такие последовательности по вертикали и горизонтали по отдельности было не сложно, но никак не могу осилить этот.

Есть предположение сделать обертку для каждого значения, и задавать в ней свойства о left, right, top, bot, обозначающие ходила ли туда проверка при поиске конкретной последовательности(т.е. чтобы при проверке 6->4-> дальше один раз уходило направо и один раз вниз). Но непонятно, как организовать такой обход.

Вот что есть на данный момент. Генерируется таблица с рандомными числами, откуда после тянутся значения. От части работает, но не всегда верно и практически всегда с переполнение стека Maximum call stack size exceeded

 //Обход матрицы, для каждого роу вызывается метод, ищущий последовательности
 for (var y = 0; y < dimension; y++) {
    for (var x = 0; x < dimension; x++) {

        wrap.x = x;
        wrap.y = y;
        wrap.needSumm = needSumm;
        wrap.left = false;
        wrap.right = false;
        wrap.top = false;
        wrap.bot = false;

        findSolution();
    }
}


function findSolution(cloneRow) {

var cloneRow;
if (cloneRow == undefined) {
    cloneRow = jQuery.extend({}, wrap);
}
var lines = $("#game tr");
var tds = $("td", lines.get(cloneRow.y));

passedElements.push($(tds.get(cloneRow.x)));

var startedVal = parseInt($(tds.get(cloneRow.x)).html());

if (startedVal < cloneRow.needSumm && summ < cloneRow.needSumm) {

    summ += startedVal;

    //check left
    if (!cloneRow.left && !isInArray($(tds.get(cloneRow.x - 1)), passedElements) && cloneRow.x - 1 > -1) {
        var leftVal = parseInt($(tds.get(cloneRow.x - 1)).html());

        if (!isInArray($(tds.get(cloneRow.x - 1)), passedElements) && leftVal + summ < cloneRow.needSumm) {
            cloneRow.x = cloneRow.x - 1;
            wrap.left = true;
            findSolution(cloneRow);
        } else if (!isInArray($(tds.get(cloneRow.x - 1)), passedElements) && leftVal + summ > cloneRow.needSumm) {
            passedElements = [];
            summ = 0;
            cloneRow.right = true;
        }
        else if (!isInArray($(tds.get(cloneRow.x - 1)), passedElements) && leftVal + summ == cloneRow.needSumm) {
            passedElements.push($(tds.get(cloneRow.x - 1)))
            var res = "";
            _.forEach(passedElements, function (n) {
                res += n.html() + " "
            })
            if (checkDuplicate(passedElements)) {
                solutions.push(passedElements);
                _.forEach(passedElements, function (n) {
                    n.css({
                        "background-color": getRandomColor()
                    })
                })
            }
            cloneRow.left = true;
            passedElements = [];
            summ = 0;
        }
    }

    //check right
    if (!cloneRow.right && !isInArray($(tds.get(cloneRow.x + 1)), passedElements) && cloneRow.x + 1 <= tds.length - 1) {
        var rightVal = parseInt($(tds.get(cloneRow.x + 1)).html());

        if (!isInArray($(tds.get(cloneRow.x + 1)), passedElements) && rightVal + summ < cloneRow.needSumm) {
            cloneRow.x++;
            findSolution(cloneRow);
        } else if (!isInArray($(tds.get(cloneRow.x + 1)), passedElements) && rightVal + summ > cloneRow.needSumm) {
            cloneRow.right = true;
            passedElements = [];
            summ = 0;
        }
        else if (!isInArray($(tds.get(cloneRow.x + 1)), passedElements) && rightVal + summ == cloneRow.needSumm) {
            passedElements.push($(tds.get(cloneRow.x + 1)))
            if (checkDuplicate(passedElements)) {
                solutions.push(passedElements);
                _.forEach(passedElements, function (n) {
                    n.css({
                        "background-color": "blue"
                    })
                })
                cloneRow.right = true;
                passedElements = [];
                summ = 0;
            }
        }
    }

    //check top
    if (cloneRow.y - 1 > -1) {
        var topLine = $("td", lines.get(cloneRow.y - 1));
        if (!cloneRow.top && !isInArray($(topLine.get(cloneRow.x)), passedElements)) {

            var topVal = parseInt($(topLine.get(cloneRow.x)).html());
            if (!isInArray($(topLine.get(cloneRow.x)), passedElements) && topVal + summ < cloneRow.needSumm) {
                cloneRow.y--;
                findSolution(cloneRow);
            } else if (!isInArray($(topLine.get(cloneRow.x)), passedElements) && topVal + summ > cloneRow.needSumm) {
                passedElements = [];
                summ = 0;
            }
            else if (!isInArray($(topLine.get(cloneRow.x)), passedElements) && topVal + summ == cloneRow.needSumm) {
                passedElements.push($(topLine.get(cloneRow.x)))
                if (checkDuplicate(passedElements)) {
                    solutions.push(passedElements);
                    _.forEach(passedElements, function (n) {
                        n.css({
                            "background-color": getRandomColor()
                        })
                    })
                }
                cloneRow.top = true;
                passedElements = [];
                summ = 0;
            }
        }
    }

    if (cloneRow.y + 1 < lines.length) {
        var botLine = $("td", lines.get(cloneRow.y + 1));

        //check bot
        if (!cloneRow.bot && !isInArray($(botLine.get(cloneRow.x)), passedElements)) {

            var botVal = parseInt($(botLine.get(cloneRow.x)).html());
            if (!isInArray($(botLine.get(cloneRow.x)), passedElements) && botVal + summ < cloneRow.needSumm) {
                cloneRow.y++;
                findSolution(cloneRow);
            } else if (!isInArray($(botLine.get(cloneRow.x)), passedElements) && botVal + summ > cloneRow.needSumm) {
                cloneRow.bot = true;
                passedElements = [];
                summ = 0;
            }
            else if (!isInArray($(botLine.get(cloneRow.x)), passedElements) && botVal + summ == cloneRow.needSumm) {
                passedElements.push($(botLine.get(cloneRow.x)))
                if (checkDuplicate(passedElements)) {
                    solutions.push(passedElements);
                    _.forEach(passedElements, function (n) {
                        n.css({
                            "background-color": getRandomColor()
                        })
                    })
                }
                cloneRow.bot = true;
                passedElements = [];
                summ = 0;
            }
        }
    }
    else {
        passedElements = [];
        summ = 0;
    }
} else {
    passedElements = [];
    summ = 0;

}
}

1 ответ 1

3

Найти все последовательности можно рекурсивным перебором.

Каждый шаг рекурсии снабжаем информацией об использованных в текущей последовательности элементах матрицы. На каждом шаге к текущей последовательности добавляем до 4-х возможных свободных соседей текущего элемента матрицы (не у каждой ячейки есть все 4 соседа). И таким образом спускаемся на уровень ниже.

Рекурсию продолжать пока есть неиспользованные элементы матрицы и выполняется условие суммы (сумма меньше M)

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.