A05_03.java

import java.util.ArrayList;
import java.util.Collections;

/**
 * Knoten
 *
 * @author Eugen Rochko
 */

class Node {

  /**
   * Name der Station
   */

  public final String name;

  /**
   * Zone der Haltestelle
   *
   * @see setZone
   */

  public String zone;

  /**
   * Ist es eine Endhaltestelle?
   *
   * @see setEndStation
   */

  public boolean endStation;

  /**
   * Wie sind wir hierher gekommen?
   *
   * @see setParent
   */

  public Node parent;

  /**
   * Verbindungen zu anderen Knoten
   */

  public final ArrayList<Edge> edges;

  /**
   * Neuen Knoten erstellen
   *
   * @param name Name der Station
   */

  public Node(String name) {
    this.name       = name;
    this.zone       = "-";
    this.endStation = false;
    this.edges      = new ArrayList<Edge>();
  }

  /**
   * Zone einstellen
   *
   * @param  zone
   * @return Node
   */

  public Node setZone(String zone) {
    this.zone = zone;
    return this;
  }

  /**
   * Endhaltestelle einstellen
   *
   * @param  isEnd Ist es eine Endhaltestelle?
   * @return Node
   */
  
  public Node setEndStation(boolean isEnd) {
    this.endStation = isEnd;
    return this;
  }

  /**
   * Vorherige Station einstellen
   *
   * @param  node Der vorherige Knoten
   * @return void
   */
  
  public void setParent(Node node) {
    this.parent = node;
  }

  /**
   * Station als String darstellen
   *
   * @return String
   */
  
  public String toString() {
    return this.name;
  }
}

/**
 * Verbindung
 *
 * @author Eugen Rochko
 */

class Edge {

  /**
   * Verbindung vom Knoten
   */

  public Node src;

  /**
   * Verbindung zum Knoten
   */

  public Node dest;

  /**
   * Neue Verbindung erstellen und zu Verbindungen des Quellknoten
   * hinzufügen
   *
   * @param src  Vom Knoten
   * @param dest Zum Knoten
   */

  public Edge(Node src, Node dest) {
    this.src  = src;
    this.dest = dest;
    src.edges.add(this);
  }

  /**
   * Verbindung als String darstellen
   *
   * @return String
   */

  public String toString() {
    return "From " + this.src + " to " + this.dest;
  }
}

/**
 * Sucher, der die Route findet
 *
 * @author Eugen Rochko
 */

class PathFinder {

  /**
   * Abgearbeitete Knoten
   */

  public final ArrayList<Node> closedList;

  /**
   * Zu bearbeitende Knoten
   */

  public final ArrayList<Node> openList;

  /**
   * Anfangsknoten
   */

  public Node start;

  /**
   * Zielknoten
   */

  public Node end;

  /**
   * Anzahl von durchgeführten Iterationen
   */

  public int count;

  /**
   * Neuen Sucher erstellen
   */

  public PathFinder() {
    this.closedList = new ArrayList<Node>();
    this.openList   = new ArrayList<Node>();
    this.count = 0;
  }

  /**
   * Route bis zum Ziel finden
   *
   * @param  start
   * @param  end
   * @return void
   */

  public void findPath(Node start, Node end) {
    this.start = start;
    this.end   = end;

    this.openList.add(start);

    while(! closedList.contains(end) && count < 500) {
      ArrayList<Node> toRemove = new ArrayList<Node>();
      ArrayList<Node> toAdd    = new ArrayList<Node>();

      for(Node node : this.openList) {
        this.closedList.add(node);
        toRemove.add(node);

        if(node != end) {
          for(Edge edge : node.edges) {
            if(this.closedList.contains(edge.dest)) {
              continue;
            } else if(! this.openList.contains(edge.dest)) {
              toAdd.add(edge.dest);
            }

            edge.dest.setParent(node);
          }
        }
      }

      this.openList.removeAll(toRemove);
      this.openList.addAll(toAdd);
    }
  }

  /**
   * Die saubere, rekonstruirte Route vom Anfang bis
   * zum Ziel
   *
   * @see getPath
   */

  private ArrayList<Node> path;

  /**
   * Die Route rekonstruiren und zurückgeben
   *
   * @return ArrayList<Node>
   */

  public ArrayList<Node> getPath() {
    this.path = new ArrayList<Node>();
    this.path.add(end);
    this.addToPath(this.end);

    Collections.reverse(this.path);

    return this.path;
  }

  /**
   * Rekursive Funktion zum Rekonstruiren der Route
   *
   * @see getPath
   * @return void
   */

  private void addToPath(Node current) {
    if(current.parent != null) {
      this.path.add(current.parent);
      this.addToPath(current.parent);
    }
  }
}

/**
 * Rechner, der die Kosten berechnet
 *
 * @author Eugen Rochko
 */

class CostCalculator {

  /**
   * Die berechneten Kosten
   */

  public float cost;

  /**
   * Neuen Rechner erstellen
   */

  public CostCalculator() {
    this.cost = 0.0f;
  }

  /**
   * Die Kosten für eine Route berechnen
   *
   * @param  path Die Route
   * @return void
   */

  public void calculateFromPath(ArrayList<Node> path) {
    String lastZone = path.get(0).zone;
    this.cost       = 3f;

    if(path.get(0).endStation) {
      this.cost += 1f;
    }

    path.remove(0);

    for(Node node : path) {
      float addCost = 0f;

      if(node.zone != lastZone) {
        addCost += 1f;
      }

      if(node.endStation) {
        addCost += 1f;
      }

      lastZone   = node.zone;
      this.cost += addCost;
    }

    if(path.size() == 1) {
      this.cost -= 1f;
    }
  }

  /**
   * Die berechneten Kosten ausgeben
   *
   * @see cost
   * @return void
   */

  public void printCost() {
    System.out.println("Kosten: " + this.cost + " Euro");
  }
}

/**
 * Hauptmodul Aufgabenblatt 05, Aufgabe 03
 *
 * @author Eugen Rochko
 */

class A05_03 {

  /**
   * Der main-Thread
   *
   * @param  args
   * @return void
   */

  public static void main(String[] args) {

    //Hier sind alle Knoten (Haltestellen)

    Node[][] nodes = new Node [6][];

    nodes[0]    = new Node [1];
    nodes[0][0] = new Node("00").setZone("A");

    nodes[1]    = new Node [5];
    nodes[1][0] = new Node("11").setZone("A");
    nodes[1][1] = new Node("12").setZone("A");
    nodes[1][2] = new Node("13");
    nodes[1][3] = new Node("14");
    nodes[1][4] = new Node("15").setEndStation(true);

    nodes[2]    = new Node [5];
    nodes[2][0] = new Node("21").setZone("A");
    nodes[2][1] = new Node("22").setZone("A");
    nodes[2][2] = new Node("23");
    nodes[2][3] = new Node("24");
    nodes[2][4] = new Node("25").setEndStation(true);

    nodes[3]    = new Node [5];
    nodes[3][0] = new Node("31").setZone("A");
    nodes[3][1] = new Node("32").setZone("A");
    nodes[3][2] = new Node("33");
    nodes[3][3] = new Node("34");
    nodes[3][4] = new Node("35").setEndStation(true);

    nodes[4]    = new Node [5];
    nodes[4][0] = new Node("41").setZone("A");
    nodes[4][1] = new Node("42").setZone("A");
    nodes[4][2] = new Node("43");
    nodes[4][3] = new Node("44");
    nodes[4][4] = new Node("45").setEndStation(true);

    nodes[5]    = new Node [5];
    nodes[5][0] = new Node("51").setZone("A");
    nodes[5][1] = new Node("52").setZone("A");
    nodes[5][2] = new Node("53");
    nodes[5][3] = new Node("54");
    nodes[5][4] = new Node("55").setEndStation(true);

    // Hier sind alle Verbindungen zwischen den Haltestellen
    // Von 00 in alle Richtungen außer 21, hin und zurück

    for(int a = 0; a < 6; a++) {
      if(a == 2) continue;
      new Edge(nodes[0][0], nodes[a][0]);
      new Edge(nodes[a][0], nodes[0][0]);
    }

    // Regelmäßige Linien, hin und zurück

    for(int b = 1; b < 6; b++) {
      for(int c = 0; c < 4; c++) {
        new Edge(nodes[b][c], nodes[b][c+1]);
        new Edge(nodes[b][c+1], nodes[b][c]);
      }
    }

    // Kreisverbindungen, hin und zurück

    for(int d = 1; d < 4; d++) {
      new Edge(nodes[d][1], nodes[d+1][1]);
      new Edge(nodes[d+1][1], nodes[d][1]);
    }

    new Edge(nodes[1][1], nodes[5][1]);

    PathFinder pathfinder1    = new PathFinder();
    CostCalculator calculator = new CostCalculator();

    // Eingabe

    System.out.print("Von:  ");
    String from = In.readLine();
    System.out.print("Nach: ");
    String to   = In.readLine();

    String[] fromParts = from.split("");
    String[] toParts   = to.split("");

    if(fromParts.length != 3 || toParts.length != 3) {
      System.out.println("Ungültige Eingabe");
      return;
    }

    int fromLine    = Integer.parseInt(fromParts[1]);
    int fromStation = Integer.parseInt(fromParts[2]) - 1;
    int toLine      = Integer.parseInt(toParts[1]);
    int toStation   = Integer.parseInt(toParts[2]) - 1;

    long startTime = System.nanoTime();

    // Route finden und Kosten berechnen

    pathfinder1.findPath(nodes[fromLine][fromStation], nodes[toLine][toStation]);
    ArrayList<Node> path = pathfinder1.getPath();
    System.out.println("Route: " + path);
    calculator.calculateFromPath(path);
    calculator.printCost();

    System.out.println("Zeit zur Berechnung gebraucht: " + ((System.nanoTime() - startTime) / 1000000000.0f) + "s");
  }
}