Метод и пример выполнения
Мы можем сделать это более эффективно, если создадим вторую сетку, в которой мы будем хранить количество шагов, которые можно сделать вверх из каждой ячейки,Давайте используем этот пример:
3 1 2 5 - - - -
4 2 5 6 - - - -
5 3 4 7 - - - -
6 7 5 4 - - - -
Мы начинаем с первой ячейки (слева вверху 3), проверяем, есть ли у нее сосед со значением 4, и если это так, мы переходим в эту ячейку и ищем5 и т. Д .;мы застреваем в ячейке со значением 7. Мы помечаем эту последнюю позицию 1 и идем назад, отмечая ячейки 2, 3, 4 и 5:
3 1 2 5 x - - - 5 - - -
4 2 5 6 x - - - 4 - - -
5 3 4 7 x - - - 3 - - -
6 7 5 4 x x - - 2 1 - -
Теперь мы знаем, что слева вверхуячейка - начало 5-ступенчатой восходящей последовательности.Затем мы переключаемся на следующую неотмеченную ячейку, 1 справа от 3;у него есть две соседние ячейки, имеющие значение 2;мы начинаем с движения вправо и застреваем в 2. Мы помечаем эту ячейку как 1 и возвращаемся к начальной точке и предварительно помечаем ее как 2.
3 1 2 5 - x x - 5 2 1 -
4 2 5 6 - - - - 4 - - -
5 3 4 7 - - - - 3 - - -
6 7 5 4 - - - - 2 1 - -
Теперь мы следуем второму пути от начальногоукажите вниз до 2 и 3, затем до 4, а затем появятся два соседних 5;мы пробуем 5, спускаясь первым, и застреваем в этой камеремы помечаем его как 1, возвращаемся к 4 и условно отмечаем 2:
3 1 2 5 - x - - 5 2 1 -
4 2 5 6 - x - - 4 - - -
5 3 4 7 - x x - 3 - 2 -
6 7 5 4 - - x - 2 1 1 -
Затем мы пробуем 5 над 4 и продолжаем, пока не застрянем на 7;мы помечаем это как 1 и возвращаемся, пока не достигнем ячейки, которую мы предварительно пометили как 2;его отметка в текущем пути будет 4, что выше, поэтому мы заменяем 2 на 4 и возвращаемся дальше, пока не достигнем начальной точки этого пути, которая была предварительно помечена 2. Новая отметка 7, поэтому мы заменим2 на 7, чтобы получить:
3 1 2 5 - x - - 5 7 1 -
4 2 5 6 - x x x 4 6 3 2
5 3 4 7 - x x x 3 5 4 1
6 7 5 4 - - - - 2 1 1 -
Мы переходим к следующей неотмеченной ячейке, которая является 5 в верхнем правом углу.У него есть один соседний 6, который уже помечен как 2, что означает, что мы можем пометить эту ячейку как 3 (вы увидите, что это действительно начало трехшагового пути от 5 до 7):
3 1 2 5 - - - x 5 7 1 3
4 2 5 6 - - - x 4 6 3 2
5 3 4 7 - - - - 3 5 4 1
6 7 5 4 - - - - 2 1 1 -
Мы переходим к следующей неотмеченной ячейке, которая является 4 в нижнем правом углу.У него есть соседняя цифра 5, которая уже помечена как 1, что означает, что мы можем пометить эту ячейку как 2.
3 1 2 5 - - - - 5 7 1 3
4 2 5 6 - - - - 4 6 3 2
5 3 4 7 - - - - 3 5 4 1
6 7 5 4 - - x x 2 1 1 2
Вторая сетка завершена, и наибольшее число, добавленное к ней, равно 7Это означает, что самая длинная последовательность в сетке имеет длину 7.
Сложность
Мы посетили каждую ячейку как часть пути и пошли назад по пути, покаввод значений во вторую сетку, поэтому сложность линейна количеству ячеек или O (N).Конечно, этот метод требует второй сетки, поэтому сложность пространства также составляет O (N).
Пример кода
Вот небольшой пример кода на JavaScript, который я написал, чтобы проверить метод и проверить свои предположения о сложности времени.Результаты можно найти под фрагментом кода.
function longestSequence(val) {
var dx = [0, 1, 0, -1], dy = [-1, 0, 1, 0]; // up, right, down, left
var height = val.length;
var width = val[0].length;
var max = 0; // max length found so far
var stack = []; // cells in the current path
var len = []; // length of upwards sequence from each cell
for (var y = 0; y < height; y++) {
len[y] = [];
for (var x = 0; x < width; x++) {
len[y][x] = 0; // initialize length grid
}
}
for (var y = 0; y < height; y++) { // iterate over every cell
for (var x = 0; x < width; x++) {
if (len[y][x] != 0) continue; // skip cells already checked
stack.push({x: x, y: y}); // start from this cell upwards ...
while (stack.length) { // and do a depth-first search
var cur = stack.pop(); // take current cell from stack
for (var i = 0; i < 4; i++) { // check four neighbouring cells
var nbr = {x: cur.x + dx[i], y: cur.y + dy[i]}; // get neighbouring cell
if (nbr.x < 0 || nbr.x == width || nbr.y < 0 || nbr.y == height) {
continue; // skip if off-grid
}
if (val[nbr.y][nbr.x] == val[cur.y][cur.x] + 1) { // neighbour has next value
if (len[nbr.y][nbr.x] == 0) { // neighbour not yet checked
stack.push(cur); // this cell is not last in path
stack.push(nbr); // move to neighbouring cell
break;
}
else if (len[nbr.y][nbr.x] >= len[cur.y][cur.x]) { // neighbour has higher length
len[cur.y][cur.x] = len[nbr.y][nbr.x] + 1; // take length from neighbour
}
}
}
if (len[cur.y][cur.x] == 0) { // no suitable neighbours ...
len[cur.y][cur.x] = 1; // cell is end-point of path
}
}
if (len[cur.y][cur.x] > max) { // new maximum length found
max = len[cur.y][cur.x];
}
}
}
return max;
}
var grid = [[3, 1, 2, 5],
[4, 2, 5, 6],
[5, 3, 4, 7],
[6, 7, 5, 4]];
document.write(longestSequence(grid));
Проверка линейной сложности
Не так просто судить о сложности этого алгоритма, глядя на код с его вложеннымпетли.Чтобы проверить мое предположение о линейности, я запустил код с сетками случайных чисел от 1 до 9 и добавил счетчик, чтобы увидеть, сколько всего ячеек было помещено в стек:
grid size cells push/pop
8 x 8 64 75
16 x 16 256 297
32 x 32 1,024 1,235
64 x 64 4,096 4,912
128 x 128 16,384 19,557
256 x 256 65,536 78,254
512 x 512 262,144 313,371
1024 x 1024 1,048,576 1,253,540
Результаты подтверждаютчто сложность действительно линейна количеству клеток.Тот факт, что количество ячеек, помещаемых в стек, составляет около 120% от числа ячеек в сетке, а не точно 100%, объясняется тем, что ячейки посещаются один, два или более раз, в зависимости от их положения на пути (конецточка, середина, перекресток).
Чтобы показать реальную скорость: приведенная выше версия JavaScript решает сетку 1024 × 1024 менее чем за секунду.