Programozás‎ > ‎Feladatok‎ > ‎Gyalogtúra‎ > ‎Megoldás‎ > ‎

ep_gyalogtura.java

Letöltés: gyalogtura.java

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;
import static java.lang.Math.sin;
import static java.lang.Math.cos;
import static java.lang.Math.sqrt;
import static java.lang.Math.atan2;


class Node{
    Node next;
    int id;
    public Node(int myid){
        next = null;
        id = myid;
    }
}

class Telepules{
    double sz,h;
    String nev;
    Node first;
   
    //beszúrás az éllista elejére
    public void insert(int id){
        Node hely = new Node(id);
        hely.next = this.first;
        this.first = hely;   
    }
   
    public Telepules(double sz, double h, String n){
        this.sz = sz;
        this.h = h;
        this.nev = new String(n);
        first = null;
    }
}

class Terkep {
    Telepules helyek[];
    int N;
   
    // gömbi távolság meghatározása
    // Vincenty-formula
    // http://en.wikipedia.org/wiki/Great-circle_distance
    public double tav(int a, int b){
        double R = 6371; // a Föld sugara
        double s1 = Math.toRadians(helyek[a].sz);
        double s2 = Math.toRadians(helyek[b].sz);
        double h1 = Math.toRadians(helyek[a].h);
        double h2 = Math.toRadians(helyek[b].h);
        double dh = h1-h2;
       
        double x =
        sqrt((cos(s2)*sin(dh))*(cos(s2)*sin(dh))+
        (cos(s1)*sin(s2)-sin(s1)*cos(s2)*cos(dh))*(cos(s1)*sin(s2)-sin(s1)*cos(s2)*cos(dh)));
        double y = sin(s1)*sin(s2)+cos(s1)*cos(s2)*cos(dh);
        double fi = atan2(x, y);
        return R*fi;
    }
   
   
    public Terkep(String fnev, int N) throws IOException{
       
        // beolvasás
        this.N = N;
        helyek = new Telepules[N];
        BufferedReader BE = new BufferedReader(new FileReader(fnev));
        for(int i = 0; i<N; i++){
            String sor = BE.readLine();
            String nev = sor.split(" ")[0];
            double sz = Double.parseDouble(sor.split(" ")[1]);   
            double h = Double.parseDouble(sor.split(" ")[2]);
            helyek[i] = new Telepules(sz,h,nev);
        }
        BE.close();
       
        // éllisták meghatározása
        for(int i = 0; i<N-1;i++)
            for(int j = i+1; j < N; j++){
                if(tav(i,j)<=20.0){
                    helyek[i].insert(j);
                    helyek[j].insert(i);
                    //System.out.println(helyek[i].nev+" "+helyek[j].nev+ " "+tav(i,j));
                }
               
            }
    }
   
    public int keres(String hely){
        int E = 0, U = N-1, K = (E+U)/2;
       
        while(E<=U && hely.compareTo(helyek[K].nev)!=0){
            if(hely.compareTo(helyek[K].nev) < 0)
                U = K - 1;
            else
                E = K + 1;
            K = (E+U)/2;
        }
        if(E<=U) return K;
        else return -1;
    }
   
    public void szomszed(int i){
        System.out.println(helyek[i].nev+" szomszédai: ");
        Node n = helyek[i].first;
       
        while(n != null){
            System.out.print(helyek[n.id].nev+" ");
            n = n.next;
        }
       
    }
}

class Bejaro{
    int d[];
    int apa[];
    boolean volt[];
    Queue<Integer> Sor;
    Terkep T;
   
    public void kiir(int hely){
        if(apa[hely]!=hely) kiir(apa[hely]);
        System.out.print(" "+T.helyek[hely].nev);
    }
   
    public void szelessegi(int START, int CEL){
        //előkészületek
        //System.out.println(T.helyek[START].nev+" -> "+T.helyek[CEL].nev);
        Sor = new LinkedList<Integer>();
        d = new int[T.N];
        apa = new int[T.N];
        volt = new boolean[T.N];
        for(int i = 0; i<T.N; i++){
            volt[i] = false;
        }
       
        d[START] = 0;
        apa[START] = START;
        volt[START] = true;;
        Sor.add(START);
       
        //bejárás
        while(!Sor.isEmpty() && !volt[CEL]){
            int x = Sor.remove();
            Node n = T.helyek[x].first;
       
            while(n != null){
                if(!volt[n.id]){
                        d[n.id] = d[x] + 1;
                        apa[n.id] = x;
                        volt[n.id] = true;
                        Sor.add(n.id);
                }
                n = n.next;
            }
           
        }
       
        //kiírás
        if(!volt[CEL]){
            System.out.println("0");
            System.out.println("LEHETETLEN");
        } else {
            System.out.print(d[CEL]);
            kiir(CEL);
            System.out.println();
        }
    }
   
    public Bejaro(Terkep mo, String fnev) throws IOException{
        T = mo;
        BufferedReader BE = new BufferedReader(new FileReader(fnev));
        int db = Integer.parseInt(BE.readLine());
        for(int i = 0; i < db; i++){
            String sor = BE.readLine();
            int START = T.keres(sor.split(" ")[0]);
            int CEL = T.keres(sor.split(" ")[1]);
            szelessegi(START, CEL);
        }   
    }
}

class gyalogtura {
    public static void main(String args[]) throws IOException{
        Terkep T = new Terkep("magyarorszag.csv",3137);
        Bejaro B = new Bejaro(T,"tura.be");
    }
}