рыцарь длины n перемещает комбинации на клавиатуре

Question

найти n комбинаций ходов коня по номерам клавиатуры от 0 до 9

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

import java.io.*;
import java.util.*;

/**
 *
 * 1 2 3 
 * 4 5 6 
 * 7 8 9 
 *   0
 *
 * when start at 1 : move L shape like knight on chess board
 * make 3-digit numbers, like this : 161, 167, 160, 181, and 183
 * total combis is: 5
 */
public class KeyPadKnight {
  public static void main(String[] args) {
    Map<Integer, List<Integer>> keyPadMap = new HashMap<>();
    keyPadMap.put(1, Arrays.asList(6, 8));
    keyPadMap.put(2, Arrays.asList(7, 9));
    keyPadMap.put(3, Arrays.asList(4, 8));
    keyPadMap.put(4, Arrays.asList(3, 9, 0));
    keyPadMap.put(6, Arrays.asList(1, 7, 0));
    keyPadMap.put(7, Arrays.asList(2, 6));
    keyPadMap.put(8, Arrays.asList(1, 3));
    keyPadMap.put(9, Arrays.asList(2, 4));
    keyPadMap.put(0, Arrays.asList(4, 6));

    int start = 1;

    int length = 3;

    int count = getCountCombi(keyPadMap, length, start);
    System.out.println("Total combi: " + count);

  }


  public static int getCountCombi(Map<Integer, List<Integer>> map, int length, Integer key) {

    int count = 0;

    count = findCombinations(key, map, length, count);

    return count;
  }

  public static int findCombinations(Integer val, Map<Integer, List<Integer>> map, int length,
      int counter) {

    if (length == 0) {
      return counter;
    }

    if (map.containsKey(val)) {
      for (Integer next : map.get(val)) {
        counter += map.get(next).size();
        findCombinations(next, map, length - 1, counter);
      }
    }
    return counter;
  }

}

Answer 1

В вашем коде есть несколько ошибок:

1.ошибка

if (map.containsKey(val)) {
   [...]
}

Это всегда будет true, эта проверка вам не нужна.Однако это лишь незначительная ошибка.

2.ошибка

 for (Integer next : map.get(val)) {
   counter += map.get(next).size();       // <-- this line
   findCombinations(next, map, length - 1, counter);
 }

Даже если использование переменной counter, как вы, сработает ( это не ), вы посчитаете промежуточные позиции одного«N step» в переменной counter, что делает его намного больше, чем должно быть.Таким образом, на каждом «уровне» вы суммируете количество возможных ходов, но в действительности вас интересуют только ровно «N шагов» длинных ходов / последовательностей.

3.ошибка

 for (Integer next : map.get(val)) {
   counter += map.get(next).size();       
   findCombinations(next, map, length - 1, counter); // <-- this line
 }

Основная проблема заключается в том, что вы думаете, что переменная counter возвращается из вашего рекурсивного вызова метода в предыдущее местоположение, где вы вызывали рекурсивный вызов. Однако это не так .Кроме того, вы не используете возвращаемое значение этого вызова метода вообще.На самом деле, ваш вызов метода в том виде, в каком он есть сейчас, не имеет никакого эффекта, и вы можете удалить его.Это покажет вам, почему ваш код возвращает неправильные результаты.

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

if (length < 1) {
    throw new IllegalArgumentException("length must be positive");
}
if (length == 1) {
   return number of jump positions from that location only
}
int sum = 0;
for (each possible jump location) {
    sum += recursive call from that location and length-1;
}
return sum;