Подсчет путей в матрице
Это вопрос из домашнего задания, с которым я застрял, и я буду счастлив, если кто-то сможет направить меня.
Законный путь определяется путем статринга в первой ячейке (строка 0 collumn 0) и отсчета до следующего шага путем добавления первой и второй цифр числа в ячейке, пока не будет достигнута последняя ячейка (строка n collumn n).
Например:
Если в ячейке [2][3] есть число 15, то следующий ход может быть:
+1 в строках и +5 в колоннами в [3][8]
или
+5 в ряду и +1 в collumns to [7][4]
Метод должен возвращать, сколько существует законных путей.
Я пытаюсь использовать рекурсивный метод обратного отслеживания для этой задачи, и я не могу использовать никакие циклы или любой другой метод, кроме методов перегрузки.
Вот код, который я придумал до сих пор:
public static int countPaths (int[][] mat)
{
return countPaths(mat,0,0);
}
private static int countPaths(int[][] mat, int col, int row)
{
if ((col==mat.length-1 && row==mat[0].length-1 ) {
return 1;
}
return countPaths(mat,mat[col][row]/10+col,mat[col][row]%10+row) + countPaths(mat,mat[col][row]%10-col,mat[col][row]/10-row);
}
Спасибо за любую помощь !
4 ответов:
Если я правильно понял проблему, это решение.
Открытый класс MatrixPathCounter { private static int [] [] мат = {{10,11,0},{10,11,10},{10,10,0}};
public static void main(String[] args) { System.out.println(countPath(mat,0,0)); } private static int countPath(int[][] mat, int x, int y) { int n = mat.length -1; if (x==n && y==n) return 1; if(x>n || y>n) return 0; if(mat[x][y]==0) return 0; if(x+mat[x][y]/10 == x+mat[x][y]%10 && x+mat[x][y]%10 == x+mat[x][y]/10) return countPath(mat,x+mat[x][y]/10,y+mat[x][y]%10); else return countPath(mat,x+mat[x][y]/10,y+mat[x][y]%10) + countPath(mat,x+mat[x][y]%10,y+mat[x][y]/10 ); }}
Как это домашнее задание , так просто несколько подсказок от меня
Вместо того, чтобы только возвращать 1, также Верните состояние сбоя. например, если столбец или строка больше длины, то возвращается 0. ( или вы можете использовать true / false)
Вы добавляете две рекурсивные функции. вместо того, чтобы делать это, попробуйте делать один за другим. Например, сначала проверьте using (row+1, com+5), если он повторяет сбой, то попробуйте (row+5, col+1).
return countPaths(mat,mat[col][row]/10+col,mat[col][row]%10+row) + countPaths(mat,mat[col][row]%10-col,mat[col][row]/10-row);"законный путь определяется путем статринга в первой ячейке (строка 0 collumn 0) и отсчета до следующего шага путем добавления первой и второй цифр числа в ячейке, пока не будет достигнута последняя ячейка (строка n collumn n).
Например: если в ячейке [2][3] есть число 15, то следующий ход может быть: +1 в строках и +5 в колумнах к [3][8] или +5 в строке и +1 в колумнах к [7][4]"
Мне кажется, что ваша логика в определении row и col отключена. определенная степень. Вы должны получать те же самые две цифры независимо, просто переключая их. Я рекомендую хранить ваши цифровые значения внутри переменной, чтобы сделать ваш код более разборчивым. Я вижу, как решить проблему, но вы ничего не узнаете, если я решу ее за вас.
Я бы также, как указал другой пользователь, убедился, что закрывает "тупиковые" пути, проверяя, являются ли они все еще допустимыми. В этот момент возвращаем 0.
Вы почти там, несколько вещей:
- Похоже, в вашем расчете возможных последующих шагов есть ошибка
- Вы должны проверить границы перед обращением к массиву / выполнением рекурсивного вызова, чтобы избежать ArrayOutOfBoundsException
Comments