Проверьте, можем ли мы путешествовать от источника к месту назначения

Question

Постановка проблемы

В Королевстве Такахаси есть архипел go из N островов, называемых островами Такахаси. Для удобства мы будем называть их Островом 1, Островом 2, ..., Островом N.

Между этими островами есть M видов регулярных лодочных рейсов. Каждая услуга соединяет два острова. I-й сервис соединяет остров ai и остров bi.

Cat Snuke сейчас находится на острове 1 и хочет go добраться до острова N. Однако оказалось, что прямого лодочного сообщения с острова нет. 1 до острова N, поэтому он хочет знать, возможно ли go до острова N с помощью двух лодок.

Если возможно go до острова N с помощью двух лодок, печать ВОЗМОЖНО; в противном случае выведите НЕВОЗМОЖНО.

Пример:

N = 3
First boat services : 1 2
Second boat services: 2 3

Вывод: ВОЗМОЖНО

Пояснение: Используя первую лодку, я могу начать с исходной точки 1 и go до 2. Теперь, используя вторую лодку, я могу go от 2 до 3, здесь 3. Мой пункт назначения.

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

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

public static String check(List<Integer> boat1, List<Integer> boat2, int N) {
        Map<Integer, Integer> first = new HashMap<>();
        for (int i = 0; i < boat1.size() - 1; i++) {
            first.put(boat1.get(i), boat1.get(i + 1));
        }

        Map<Integer, Integer> second = new HashMap<>();
        for (int i = 0; i < boat2.size() - 1; i++) {
            second.put(boat2.get(i), boat2.get(i + 1));
        }

        if (first.get(1) != null) {
            int island = first.get(1);
            if (second.get(island) != null) {
                island = second.get(island);
                if (island == N) {
                    return "POSSIBLE";
                }
            }
        }
        return "Impossible";
    }

Обновление:

Допустим, услуги лодки 1 - это 1, 2, 3, 4 и лодка 2 услуги 3,5. Попытка ответить Josep сейчас:

public static void main(String[] args) {
    GrafDirLlistes s = new GrafDirLlistes(5);
    s.afegirAresta(1, 2, 1);
    s.afegirAresta(2, 3, 1);
    s.afegirAresta(3, 4, 1);
    s.afegirAresta(3, 5, 1);
    s.dfs();
    System.out.println(s.existeixAresta(1, 5));

}

Я ожидаю истины для вышеуказанной программы, поскольку мы можем перемещаться от 1 до 5, как это 1-> 2-> 3-> 5, но программа возвращает false.

Answer 1

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

public class GrafDirLlistes {
ArrayList<Adj>[] elArray; //This is where we store the adjacent vertex to the current vertex

    boolean[] visitOrder;
    int[] path;

    public GrafDirLlistes(int numVert) {
        elArray = new ArrayList[numVert];
        for (int i = 0; i < elArray.length; i++) {
            elArray[i] = new ArrayList();
        }
    }

public boolean existeixAresta(int v_orig, int v_desti) { //Method to check wheter an edge exists
        if (v_orig < 0 || v_orig >= elArray.length) {
            return false;
        }

        for (int i = v_orig; i < elArray[v_orig].size(); i++) {
            if (elArray[v_orig].get(i).vertDest == v_desti) {
                return true;
            }
        }
        return false;
    }
    public boolean afegirAresta(int v_orig, int v_dest, double pes) { // Method to add a new edge

        if (v_orig < 0 || v_orig >= elArray.length || v_dest < 0 || v_dest >= elArray.length) {
            return false;
        }

        if (existeixAresta(v_orig, v_dest)) {
            return false;
        }

        elArray[v_orig].add(new Adj(v_dest, pes));
        return true;
    }

Здесь мы создаем граф, помещая их в массив arrayylist. Функция массива - видеть, какие вершины являются смежными. Например, если у нас есть график, в котором 0 указывает на 1, elArray [0] будет иметь ArrayList только с 1 элементом, 1, то есть вершиной, на которую указывает 0. Класс Adj

public class Adj {

    public int vertDest;
    public double weight;

    public Adj(int v, double p) {
        vertDest = v;
        weight = p;
    }

}

Метод Dfs:

    public void dfs() {
        visitOrder = new boolean[elArray.length];
        path = new int[elArray.length];
        for (int v = 0; v < elArray.length; v++) {
            path[v] = -1;
        }

        for (int v = 0; v < elArray.length; v++) {
            if (!visitOrder[v]) {
                dfs(v);
            }
        }
    }

    private void dfs(int orig) {
        visitOrder[orig] = true;

        for (int i = 0; i < elArray[i].size(); i++) {
            int v_dest = elArray[orig].get(i).vertDest;
            if (!visitOrder[v_dest]) {
                path[v_dest] = orig;
                dfs(v_dest);
            }
        }
    }

Теперь, когда вы завершаете sh dfs (), вам нужно только проверить массив путей, здесь будет сохранен, если путь существует от x до y

Answer 2

Услуги представляют собой пары целых чисел [от, до]. Сначала вам нужно найти набор островов, на которые можно попасть из 1 за один шаг. Затем используйте все это и создайте новый набор всего, что можно получить из любого из них еще одним шагом. У вас есть некоторые элементы из этого, но вам не хватает некоторых ингредиентов. Правильное использование Map и Set сделает это вычисление очень эффективным. Основные причины использования Set заключаются в том, что он решает проблему, когда на данный остров можно попасть более чем по одному пути, и очень быстро проверяется, содержат ли острова, доступные на втором этапе, тот, который вас интересует. .

Вот один из способов реализации. Java потоки упрощают работу.

class Length2Paths {
  private static final Set<Integer> NONE = (Set<Integer>) EMPTY_SET;

  static class Service {
    final int from, to;
    public Service(int from, int to) {
      this.from = from;
      this.to = to;
    }
  }

  static Set<Integer> getReachableIn2Steps(int from, List<Service> services) {
    Map<Integer, Set<Integer>> edges = 
        services.stream().collect(groupingBy(s -> s.from, mapping(s -> s.to,  toSet())));
    Set<Integer> reachableIn1Step = edges.getOrDefault(from, NONE);
    return reachableIn1Step.stream().flatMap(i -> edges.getOrDefault(i, NONE).stream()).collect(toSet());
  }

  static void printIfPossibleIn2StepsFrom1(int destination, List<Service> services) {
     System.out.println(getReachableIn2Steps(1, services).contains(destination) ? "POSSIBLE" : "IMPOSSIBLE");
  }

  public static void main(String [] args) {
    Service [] services = { new Service(1, 2), new Service(2, 3) };
    printIfPossibleIn2StepsFrom1(3, Arrays.asList(services));
    printIfPossibleIn2StepsFrom1(2, Arrays.asList(services));
  }
}

Это печатает:

POSSIBLE
IMPOSSIBLE

Answer 3

Вы можете сделать это в однопроходном стиле

// all the "left" points of boats which ends in N
endingBoats = new Set // (e.g for boat [2,N] you store 2)

// all the "right" points of boats which start with 1
startingBoats = new Set // (e.g for boat [1, 3] your store 3)

for all boats:
  if boats does not start with 1 or end with N:
    continue

  // if boat starts with 1
  if boat[0] == 1:
    // check if there is a junction with a boat ending in N
    if endingBoats.has(boat[1]):
      return 'possible'
    // if not add the starting boat to candidates for junction
    startingBoats.add(boat[1])

  // if boat ends with N
  else if boat[1] == N:
    // check if there is a junction with a starting boat
    if startingBoats.has(boat[0]):
      return 'possible'
    // if not add the ending boat to candidates for junction
    endingBoats.add(boat[0])
return 'not possible'