Как распечатать путь, выбранный BFS? - PullRequest
Новая
       52

Как распечатать путь, выбранный BFS?

0 голосов
/ 31 марта 2020

Я работаю над проблемой из Leetcode, где мы данной комбинации замка, чтобы добраться от начальной комбинации 0000. Вы можете только вращать один блокировку колес в то время, и вы должны сделать это, используя в качестве нескольких витков, как возможный. У меня есть решение для этого, и оно работает нормально, но я не знаю, как на самом деле распечатать путь, который BFS использует для достижения этого решения (то есть промежуточные комбинации, используемые для его достижения). Любая помощь будет оценена! 

class Solution {

    private static final String START = "0000";

    public int openLock(String[] deadends, String target) {
        if (target == null || target.length() == 0) return -1;
        Set<String> visited = new HashSet<>(Arrays.asList(deadends));
        Queue<String> queue = new LinkedList<>();
        int level = 0;
        queue.offer(START);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String currentLock = queue.poll();
                if (!visited.add(currentLock)) continue;
                if (currentLock.equals(target)) return level;

                for (String nextLock : getNextStates(currentLock)) {
                    if (!visited.contains(nextLock)) queue.offer(nextLock);
                }
            }
            level++;
        }

        return -1;
    }

    private List<String> getNextStates(String lock) {
        List<String> locks = new LinkedList<>();
        char[] arr = lock.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            arr[i] = c == '9' ? '0' : (char) (c + ((char) 1));
            locks.add(String.valueOf(arr));
            arr[i] = c == '0' ? '9' : (char) (c - ((char) 1));
            locks.add(String.valueOf(arr));
            arr[i] = c;
        }
        return locks;
    }
}

Ответы [ 2 ]

0 голосов
/ 31 марта 2020

Как сказал @Tarun, вы можете сохранить отношения ребенка с родителем. Есть лучший способ, которым я воспользовался, но сначала я собираюсь рассказать о том, какие у вас другие проблемы. Во-первых, вы делаете это: Set<String> visited = new HashSet<>(Arrays.asList(deadends)); Arrays.asList(...) в вашем случае должно принимать каждый String в deadends. Итак, вы должны изменить это на следующее: 

HashSet<String> set = new HashSet<>();
for(String s : deadends) {
    set.add(s);
}

Конечно, переименуйте его в visited, я просто копирую и вставляю материал из моего принятого решения. Кроме того, то, как вы используете Queue, не является неправильным, но если вы берете все из него сразу, а затем добавляете новые значения, вы также можете использовать LinkedList или ArrayList. Вы должны получать записи из Queue одну за другой, а Queue помещает новые записи позже, так что вам не нужно беспокоиться о пропуске.

Лучший метод для отслеживания количество сделанных вами ходов хранится в самом Queue. Вы сохраняете текущую комбинацию и количество шагов, предпринятых для ее достижения. Итак, когда вы найдете ответ, просто верните вторую запись, количество шагов. Если вы выйдете из l oop, верните -1. Вот мое принятое решение, использующее все это: 

class Solution {

    public int openLock(String[] deadends, String target) {
        HashSet<String> set = new HashSet<>();
        for(String s : deadends) {
            set.add(s);
        }

        HashSet<String> visited = new HashSet<>();
        Queue<Pair<String, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>("0000", 0));

        while(!queue.isEmpty()) {
            Pair<String, Integer> curr = queue.poll();

            if(set.contains(curr.first) || !visited.add(curr.first)) {
                continue;
            } else if(curr.first.equals(target)) {
                return curr.second;
            } else {
                LinkedList<String> next = next(curr.first);

                for(String s : next) {
                    queue.offer(new Pair<>(s, curr.second + 1));
                }
            }
        }

        return -1;
    }

    private LinkedList<String> next(String string) {
        LinkedList<String> ans = new LinkedList<>();
        ans.add(String.valueOf(new char[]{minus(string.charAt(0)), string.charAt(1), string.charAt(2), string.charAt(3)}));
        ans.add(String.valueOf(new char[]{plus(string.charAt(0)), string.charAt(1), string.charAt(2), string.charAt(3)}));
        ans.add(String.valueOf(new char[]{string.charAt(0), minus(string.charAt(1)), string.charAt(2), string.charAt(3)}));
        ans.add(String.valueOf(new char[]{string.charAt(0), plus(string.charAt(1)), string.charAt(2), string.charAt(3)}));
        ans.add(String.valueOf(new char[]{string.charAt(0), string.charAt(1), minus(string.charAt(2)), string.charAt(3)}));
        ans.add(String.valueOf(new char[]{string.charAt(0), string.charAt(1), plus(string.charAt(2)), string.charAt(3)}));
        ans.add(String.valueOf(new char[]{string.charAt(0), string.charAt(1), string.charAt(2), minus(string.charAt(3))}));
        ans.add(String.valueOf(new char[]{string.charAt(0), string.charAt(1), string.charAt(2), plus(string.charAt(3))}));
        return ans;
    }

    private char minus(char c) {
        return c == '0' ? '9' : (char) ((int) c - 1);
    }

    private char plus(char c) {
        return c == '9' ? '0' : (char) ((int) c + 1);
    }

    private class Pair<E, T> {
        E first;
        T second;

        Pair(E e, T t) {
            first = e;
            second = t;
        }
    }

}
0 голосов
/ 31 марта 2020

Я думаю, что вы можете сделать это sh, поддерживая отношения между родителями и детьми. 

    Map<String,String> childToParent = new HashMap<String,String>();
    String currentLock = null;
    boolean found = false;
    while (!queue.isEmpty() && !found) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String currentLock = queue.poll();
            if (!visited.add(currentLock)) continue;
            if (currentLock.equals(target)){
                found = true;
                break;
            }
            for (String nextLock : getNextStates(currentLock)) {

                if (!visited.contains(nextLock)){
                   queue.offer(nextLock);
                   childToParent.put(nextLock,currentLock);
                  }
            }
        }
        level++;
    }
    if(!found){
     return -1;
    }
    // Printing path 
    int level = 0;
    while(childToParent.get(currentLock) != null){
        System.out.println(currentLock);
        currentLock = childToParent.get(currentLock);
        level++; 
    }
    System.out.println(currentLock);
    return level;
...