отличается для петель Java

Question

У меня возникли некоторые трудности со следующей проблемой:

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

Доступные направления: N (ord), E (ast), S, W.Я использую функцию getPosDirections, чтобы получить возможные направления этого места.Функция возвращает направления в ArrayList<String>, например, для пятна J3: [E,W]

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

Я хочу ArrayList из всех возможных маршрутов

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

(x равен числу, брошенному костью).

Например: я бросаю 3, и в данный момент я нахожусь на месте J3:

[[E,N,E],[E,N,S],[E,S,E],[E,S,S],[W,N,E],[W,N,S],[W,S,E],[W,S,S]]

Как получить последний упомянутый массив (список)?

Answer 1

Во-первых, вы можете подумать о своем подходе еще немного. В худшем случае (бросается 12, и все 4 направления возможны в каждом месте), будет 4 ^ 12 ~ = 160 миллионов маршрутов. Действительно ли необходимо перебирать их всех? И нужно ли заполнять около 1 ГБ памяти для хранения этого списка?

Далее, вероятно, будет хорошей идеей представлять направления безопасным для типов образом, например, используя enum.

Как говорится, рекурсия - твой друг:

private void iteratePaths(Location currentLoc, List<Direction> currentPath, List<List<Direction>> allPaths, int pathLength) {
    if (currentPath.size() >= pathLength) {
        allPaths.add(new ArrayList<Direction>(currentPath));
        return;
    }
    for (Direction d : currentLoc.getPosDirections()) {
        currentPath.add(d);
        Location newLoc = currentLoc.walk(d);

        iteratePaths(newLoc, currentPath, allPaths, pathLength);

        currentPath.remove(currentPath.size() - 1);
    }
}

public void List<List<Direction>> getAllPaths(Location loc, int length) {
    List<List<Direction>> allPaths = new ArrayList<List<Direction>>();
    List<Direction> currentPath = new ArrayList<Direction>();
    iteratePaths(loc, currentPath, allPaths, length);
    return allPaths;
}

Answer 2

Вы можете предположить, что ваше поле пятен представляет собой полный график .Затем вам нужно реализовать BFS или DFS с сохранением путей.

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