Aufgabe 3

BugwartsPathFinder.java

package rla;

import java.util.*;

public class BugwartsPathFinder {
    private static final char WALL = '#';
    private static final char START = 'A';
    private static final char END = 'B';

    public static void main(String[] args) {
        // Schulplan einlesen
        char[][][] schoolMap = SchoolMapReader.readMap();

        // Graphen auf Basis des Schulplans erstellen
        Node startNode = null;
        Node endNode = null;
        Map<String, Node> nodes = new HashMap<>();

        for (int floor = 0; floor < schoolMap.length; floor++) {
            for (int row = 0; row < schoolMap[floor].length; row++) {
                for (int col = 0; col < schoolMap[floor][row].length; col++) {
                    char currentChar = schoolMap[floor][row][col];
                    if (currentChar != WALL) {
                        String key = floor + "-" + row + "-" + col;
                        Node node = new Node(floor, row, col);
                        nodes.put(key, node);

                        if (currentChar == START) {
                            startNode = node;
                        } else if (currentChar == END) {
                            endNode = node;
                        }
                    }
                }
            }
        }

        // Verbindungen zwischen den Knoten herstellen
        for (Node node : nodes.values()) {
            addNeighbors(node, schoolMap, nodes);
        }

        // Dijkstra-Algorithmus anwenden
        dijkstra(startNode);

        // Den kürzesten Weg finden und ausgeben
        List<Node> path = getShortestPathTo(endNode);
        printPath(path);
    }

    private static void addNeighbors(Node node, char[][][] map, Map<String, Node> nodes) {
        int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // Bewegungsrichtungen
        for (int[] dir : directions) {
            int newX = node.x + dir[0];
            int newY = node.y + dir[1];
            String key = node.floor + "-" + newX + "-" + newY;

            if (newX >= 0 && newX < map[node.floor].length &&
                newY >= 0 && newY < map[node.floor][newX].length &&
                map[node.floor][newX][newY] != WALL) {
                node.addNeighbor(nodes.get(key));
            }
        }
    }

    private static void dijkstra(Node startNode) {
        startNode.setDistance(0);
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(Node::getDistance));
        queue.add(startNode);

        while (!queue.isEmpty()) {
            Node current = queue.poll();

            for (Node neighbor : current.getNeighbors()) {
                int newDist = current.getDistance() + 1;
                if (newDist < neighbor.getDistance()) {
                    neighbor.setDistance(newDist);
                    neighbor.previous = current;
                    queue.add(neighbor);
                }
            }
        }
    }

    private static List<Node> getShortestPathTo(Node endNode) {
        List<Node> path = new ArrayList<>();
        for (Node node = endNode; node != null; node = node.previous) {
            path.add(node);
        }
        Collections.reverse(path);
        return path;
    }

    private static int calculateTotalTime(List<Node> path) {
      if (path.isEmpty()) {
          return 0;
      }
  
      int totalTime = 0;
      Node previousNode = path.get(0);
  
      for (int i = 1; i < path.size(); i++) {
          Node currentNode = path.get(i);
          if (currentNode.floor == previousNode.floor) {
              totalTime += 1; // 1 Sekunde für Bewegung auf der gleichen Etage
          } else {
              totalTime += 3; // 3 Sekunden für den Wechsel zwischen Etagen
          }
          previousNode = currentNode;
      }
  
      return totalTime;
  }

    private static void printPath(List<Node> path) {
        for (Node node : path) {
            System.out.println(node);
        }

        int totalTime = calculateTotalTime(path);
        System.out.println("Gesamtzeit: " + totalTime + " Sekunden");
    }
}

Node.java

package rla;
import java.util.ArrayList;
import java.util.List;

public class Node implements Comparable<Node> {
    int floor, x, y;
    List<Node> neighbors;
    Node previous;
    int distance;

    public Node(int floor, int x, int y) {
        this.floor = floor;
        this.x = x;
        this.y = y;
        this.neighbors = new ArrayList<>();
        this.distance = Integer.MAX_VALUE;
    }

    public void addNeighbor(Node neighbor) {
        this.neighbors.add(neighbor);
    }

    public int getDistance() {
        return this.distance;
    }

    public void setDistance(int distance) {
        this.distance = distance;
    }

    public List<Node> getNeighbors() {
        return this.neighbors;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.distance, other.distance);
    }

    @Override
    public String toString() {
        return "Node(" + floor + ", " + x + ", " + y + ")";
    }
}

SchoolMapReader.java

package rla;

import java.util.Scanner;

public class SchoolMapReader {
    public static char[][][] readMap() {
        Scanner scanner = new Scanner(System.in);

        // Größe des Plans einlesen
        int rows = scanner.nextInt();
        int columns = scanner.nextInt();
        scanner.nextLine(); // Zeilenende überspringen

        // 3D-Array für die Etagen erstellen
        char[][][] schoolMap = new char[2][rows][columns];

        // Den Plan für jede Etage einlesen
        for (int floor = 0; floor < 2; floor++) {
            for (int row = 0; row < rows; row++) {
                String line = scanner.nextLine();
                for (int col = 0; col < columns; col++) {
                    schoolMap[floor][row][col] = line.charAt(col);
                }
            }
            if (floor < 1) {
                scanner.nextLine(); // Leere Zeile zwischen den Etagen überspringen
            }
        }

        scanner.close();
        return schoolMap;
    }
}