Найти самый длинный путь в матрицу, в которой каждый шаг имеет записи, которые отличаются на 1


Дали П*П матрица, все числа различны в нем функция должна найти максимальная длина пути (начиная с любой клетки) таким образом, что все клетки на пути в порядке возрастания с разницей в 1.

Он может двигаться в 4 направлениях от заданной ячейке (i, j), то он может двигаться на (i-1, j) или (Я, J-1) или (i+1, j) или (Я, J+1) при условии, что соседние ячейки имеют разницу 1.

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

Меня не устраивает форма и структура мой код, потому что я прошел через рекурсию шаг за шагом по всем вариантам. Я пытаюсь написать это в виде отката с разметкой клетки и стоп-условия.

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

public static int longestWorm(int[][] mat){
    return longestWorm(mat, 0,0,0);
}

private static int longestWorm(int[][] mat,int i, int j, int max){
    if (i == mat.length) return max;
    if (j == mat[i].length-1)
        return longestWorm(mat, i + 1, 0, max);
    if (wormCount(mat,i,j,0) > max) 
        max = wormCount(mat,i,j,0);
    return longestWorm(mat, i, j + 1, max);
}
private static int wormCount(int[][] mat, int i, int j,int count){
    if(i < mat.length-1 && mat[i][j] == mat[i+1][j]+1) 
        return 1+ wormCount(mat, i+1, j, count+1);
    if(j < mat[i].length-1 && mat[i][j] == mat[i][j+1]+1) 
        return 1+ wormCount(mat, i, j+1, count+1);
    if(i > 0 && mat[i][j] == mat[i-1][j]+1) 
        return 1+ wormCount(mat, i-1, j, count+1); 
    if(j > 0 && mat[i][j] == mat[i][j-1]+1)
        return 1+ wormCount(mat, i, j-1, count+1);
    return count;
}


697
2
задан 2 марта 2018 в 09:03 Источник Поделиться
Комментарии
3 ответа

Так пару замечаний:


  • Если я правильно понял требуется решение, вы, кажется, есть ошибка, например longestWorm(new int[][]{{0, 1, 3}, {9, 8 ,7}, {4, 5, 6}}) возвращает 10, хотя там всего 9 номеров. В wormcount расчет то неправильно, потому что вы два раза инкремент счетчика, а не один раз. Рекурсивное определение проблемы, вы можете сказать, что длина пути-длина текущей ячейки (которая одна), суммируясь по длине оставшегося пути. Что бы сделать длину функция что-то вроде:

    private static int wormCount(int[][] mat, int i, int j){
    if (i < mat.length - 1 && mat[i][j] == mat[i + 1][j] + 1) {
    return 1 + wormCount(mat, i + 1, j);
    }
    ....
    return 1;
    }

Это также делает базовом варианте очень понятно. Вам также не обязательно нужно передать переменную count. Только возможно, если вы хотели бы сделать ее хвост-рекурсивной функции, но, насколько мне известно, в Java это не поможет устранить переполнение стека.


  • Проблема определяется как найти путь возрастания, но код, кажется, рассчитают все с точностью до наоборот. Не ошибаешься, но немного сбивает с толку.

  • В longestWorm функции, вычислить одну и ту же функцию дважды. В этом нет необходимости:

    max = Math.max(max, wormCount(mat, i, j, 0));

Вы могли бы сохранить его в локальной переменной, если она помогает readeability.

Я не знаю оптимальный способ решить эту проблему. Я думаю, вы бы могли по каждому индексу вычислить длину пути, и сохранить его в таблице. Поскольку каждое значение является уникальным, он может быть просто карту между стоимостью и длина пути, начиная с этого значения (иначе это может быть просто ключ, сгенерированный с помощью индексов я и Джей). Перед расчетом продолжительности определенного значения (или начиная с определенного индекса), вы сначала посмотрите, если вы уже рассчитали ее, которые потом можно повторно использовать.

2
ответ дан 3 марта 2018 в 12:03 Источник Поделиться

В соответствии с @Koekje интересные рекомендации, я отредактировал код так, что базовый вариант является более понятной, а также потому, что ошибка была обнаружена в коде.
Было также рекомендовано Koekje, конечно, использовать максимальный ток, чтобы избежать перекодирования и пересчет. Теперь код выглядит короче и более читабельным. Конечно, хотелось бы видеть больше комментариев/выводы.

public static int longestWorm(int[][] mat){
return longestWorm(mat, 0,0,0);
}

private static int longestWorm(int[][] mat,int i, int j, int max){
if (i == mat.length) return max;
if (j == mat[i].length)
return longestWorm(mat, i + 1, 0, max);
max= Math.max(max,wormCount(mat,i,j));
return longestWorm(mat, i, j + 1, max);
}
private static int wormCount(int[][] mat, int i, int j){
if(i < mat.length-1 && mat[i][j] == mat[i+1][j]+1)
return 1+ wormCount(mat, i+1, j);
if(j < mat[i].length-1 && mat[i][j] == mat[i][j+1]+1)
return 1+ wormCount(mat, i, j+1);
if(i > 0 && mat[i][j] == mat[i-1][j]+1)
return 1+ wormCount(mat, i-1, j);
if(j > 0 && mat[i][j] == mat[i][j-1]+1)
return 1+ wormCount(mat, i, j-1);
return 1;
}

0
ответ дан 3 марта 2018 в 01:03 Источник Поделиться

После консультаций с другими студентами и после бесконечных дискуссий по поводу этого вопроса, окончательное решение этого кода:

public static int worm(int[][] a,int i,int j,int lastValue,boolean start)
{
if(i<0||i==a.length||j<0||j==a[0].length)
return 0;

if(lastValue == a[i][j] - 1 || start==true)
{
int l = worm(a,i,j-1,a[i][j],false);
int r = worm(a,i,j+1,a[i][j],false);
int u = worm(a,i-1,j,a[i][j],false);
int d = worm(a,i+1,j,a[i][j],false);
return 1 + Math.max(Math.max(l,r),Math.max(u,d));
}
return 0;
}

public static int longestWorm2(int[][] a,int i,int j,int max)
{
if(i==a.length)
return max;
if(j==a[0].length)
return longestWorm2(a,i+1,0,max);
max = Math.max(max, worm(a,i,j,a[i][j],true));
return longestWorm2(a,i,j+1,max);
}
public static int longestWorm2(int[][] a){
return longestWorm2(a,0,0,1);
}

0
ответ дан 5 марта 2018 в 05:03 Источник Поделиться