Нижняя матрица слева сверху справа


Может кто-то пожалуйста, ознакомьтесь с этой простой код для печати все пути в матрице из нижнего левого угла в верхний правый? Если элемент равен 1, это "стена" и вы не можете взять его.

Возможные шаги: вверх и вправо

  // Prints possible paths from bottom left to top right
    public static void findPath(int n, int i , int j, int[][] mat,ArrayList<Integer> path)
    {
        if(i==0 && j==n-1)
        {
            System.out.println();
            for(Integer step: path)
            {
                System.out.print(","+step);
            }
        }

        if(isPossibleStep(i+1,j,n,mat))
        {
            path.add(i+1);
            findPath(n,i+1, j,mat, path);
        }
        else if(isPossibleStep(i,j-1,n,mat))
        {
            path.add(j-1);
            findPath(n,i, j-1,mat, path);
        }

    }

    // Tells if a given path is possible
    public static boolean isPossibleStep(int i, int j, int n,int[][] mat)
    {
        if(mat[i][j]==1)
            return false;

        if(i < n && j > 0)
            return true;
        else
            return false;
    }

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



1790
1
задан 28 июня 2011 в 03:06 Источник Поделиться
Комментарии
2 ответа

Вы можете выполнить рефакторинг findPath логика несколько и уменьшить отступ уровня при сохранении метода поведения:

// Prints possible paths from bottom left to top right
public static void findPath(int n, int i , int j, int[][] mat, ArrayList<Integer> path)
{
if(i == 0 && j == n - 1)
{
System.out.println();
for(Integer step: path)
{
System.out.print("," + step);
}
}

boolean rightStep = isPossibleStep(i + 1, j, n, mat);
if(!isPossibleStep(i, j - 1, n, mat) && !rightStep)
return;

path.add(rightStep ? ++i : --j);
findPath(n, i, j, mat, path);
}

isPossibleStep также может быть упрощено путем использования короткого замыкания логики. Следующие выражает намерение непосредственно с будучи немногословным:

public static boolean isPossibleStep(int i, int j, int n, int[][] mat)
{
return mat[i][j] != 1
&& i < n
&& j > 0;
}

1
ответ дан 28 июня 2011 в 08:06 Источник Поделиться

Интересно, какая польза от добавления просто я+1 или J-1 в пути. Не стоит путь состоит из индекса пар (я,J)?

Опираясь на ответ Виктора, вот еще несколько оптимизаций:

public static void findPath(int n, int i, int j, int[][] mat, ArrayList<Integer> path) {
if (i == 0 && j == n-1) {
System.out.println(path); // (1)
}

Integer step; // (2)
if (isPossibleStep(i + 1, j, n, mat)) {
step = ++i;
} else if (isPossibleStep(i, j - 1, n, mat)) {
step = --j;
} else {
return;
}

path.add(step);
findPath(n, i, j, mat, path);
}

public static boolean isPossibleStep(int i, int j, int n, int[][] mat) {
return i < n && j >= 0 // (3)
&& mat[i][j] != 1;
}

Примечания:


  1. Вместо зацикливания коллекцию, чтобы распечатать его, класса ArrayListс методом toString() метод может сделать это (с большей производительностью). Если вы не хотите печатать квадратные скобки, просто делать подстроку:

    String pathStr = path.toString();
    System.out.println(pathStr.substring(1, pathStr.length()-1);

  2. Кода вокруг временного шага переменных можно упростить, если вы используете индекс пары для представления пути.

  3. Метод isPossibleStep должны проверить индексы , прежде чем он пытается получить доступ к матрице. В противном случае вы могли бы в конечном итоге с ArrayIndexOutOfBoundsException. Также обратите внимание, что я проверяю в j >= 0, поскольку 0 является допустимым индексом. (Вы должны также проверить, что я >= 0 && j в < Н чтобы быть безопасным.)

0
ответ дан 28 июня 2011 в 10:06 Источник Поделиться