API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Mar 31st, 2019
75
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 15.89 KB | None | 0 0
raw download clone embed print report
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class Point{
  5.     public int x;
  6.     public int y;
  7.     public Point(){
  8.         x = 0;
  9.         y = 0;
  10.     }
  11.     public Point (int x, int y){
  12.         this.x = x;
  13.         this.y = y;
  14.     }
  15.     public void print(){
  16.         System.out.println("X = "+x+" Y = "+y);
  17.     }
  18.  
  19.     public double jarakDuaTitik(Point b){
  20.         return (Math.sqrt(((this.x-b.x)*(this.x-b.x))+((this.y-b.y)*(this.y-b.y))));
  21.     }
  22. }
  23.  
  24. class Node{
  25.     public ArrayList<Point> P;
  26.     public double cost;
  27.  
  28.     public Node(){
  29.         this.P = new ArrayList<Point>();
  30.         this.cost = 0;
  31.     }
  32.  
  33.     public void copyNode(Node N){
  34.         for (int i = 0;i<N.P.size();i++){
  35.             P.add(N.P.get(i));
  36.         }
  37.     }
  38. }
  39.  
  40. class labirin{
  41.     public boolean[][] matriks;
  42.     public Point start;
  43.     public int baris;
  44.     public int kolom;
  45.     public int[][] matriksInt;
  46.     public ArrayList<Point> currentList;
  47.     public Node currentNode;
  48.  
  49.     public labirin(int baris, int kolom){
  50.         this.baris = baris;
  51.         this.kolom = kolom;
  52.         matriks = new boolean[baris][kolom];
  53.         matriksInt = new int[baris][kolom];
  54.         start = new Point();
  55.         currentList = new ArrayList<Point>();
  56.         currentNode = new Node();
  57.     }
  58.    
  59.     public void printLabirin(){
  60.         for (int i = 0;i< baris;i++){
  61.             for (int j = 0;j<kolom;j++){
  62.                 if (matriks[i][j] == true){
  63.                     System.out.print("1");
  64.                 }else{
  65.                     System.out.print("0");
  66.                 }
  67.             }
  68.             System.out.println();
  69.         }
  70.     }
  71.  
  72.     public void transferMatriks(){
  73.         int i,j;
  74.         for(i = 0;i<baris;i++){
  75.             for(j = 0;j<kolom;j++){
  76.                 if (matriks[i][j]){
  77.                     matriksInt[i][j] = 1;
  78.                 }else{
  79.                     matriksInt[i][j] = 0;
  80.                 }
  81.             }
  82.         }
  83.     }
  84.  
  85.     public void findStart(){
  86.         boolean found = false;
  87.         int i = 0;
  88.         while ((!found)&&(i<kolom)){
  89.             if (!matriks[0][i]){
  90.                 start.x = i;
  91.                 start.y = 0;
  92.                 found = true;
  93.             }
  94.             if ((!matriks[baris-1][i])&&(!found)){
  95.                 start.x = i;
  96.                 start.y = baris-1;
  97.                 found = true;
  98.             }
  99.             i++;
  100.         }
  101.         i = 0;
  102.         while ((!found)&&(i<baris)){
  103.             if (!matriks[i][0]){
  104.                 start.x = 0;
  105.                 start.y = i;
  106.                 found = true;
  107.             }
  108.             if ((!matriks[i][kolom-1])&&(!found)){
  109.                 start.x = kolom-1;
  110.                 start.y = i;
  111.                 found = true;
  112.             }
  113.             i++;
  114.         }
  115.     }
  116.  
  117.     public void copyList(ArrayList<Point> dari, ArrayList<Point> ke){
  118.         for (int i = 0;i<dari.size();i++){
  119.             ke.add(dari.get(i));
  120.         }
  121.     }
  122.  
  123.     public void solveBFS(){ //Menyelesaikan dengan algoritma BFS
  124.         currentList.clear();
  125.         ArrayList<ArrayList<Point>> queue = new ArrayList<ArrayList<Point>>();
  126.         Point currentPoint = new Point(start.x, start.y);
  127.         // ArrayList<Point> currentList = new ArrayList<Point>();
  128.         boolean[][] matriksSudahDikunjungi = new boolean[baris][kolom];
  129.         matriksSudahDikunjungi[start.y][start.x] = true;
  130.         currentList.add(currentPoint);
  131.         //System.out.println("Titik awal adalah : X="+currentPoint.x+" Y="+currentPoint.y);  
  132.         if (currentPoint.x == 0){
  133.             currentList.add(new Point(currentPoint.x+1,currentPoint.y));
  134.         }
  135.         if (currentPoint.x == kolom-1){
  136.             currentList.add(new Point(currentPoint.x-1,currentPoint.y));
  137.         }
  138.         if (currentPoint.y == 0){
  139.             currentList.add(new Point(currentPoint.x,currentPoint.y+1));
  140.         }
  141.         if (currentPoint.y == baris-1){
  142.             currentList.add(new Point(currentPoint.x,currentPoint.y-1));
  143.         }
  144.         currentPoint = currentList.get(currentList.size()-1);
  145.         while ((currentPoint.x!=0)&&(currentPoint.x!=kolom-1)&&(currentPoint.y!=0)&&(currentPoint.y!=baris-1)){
  146.             matriksSudahDikunjungi[currentPoint.y][currentPoint.x] = true;
  147.             if (!matriks[currentPoint.y][currentPoint.x+1]){
  148.                 if(!matriksSudahDikunjungi[currentPoint.y][currentPoint.x+1]){
  149.                     ArrayList<Point> prevList = new ArrayList<Point>();
  150.                     copyList(currentList,prevList);
  151.                     prevList.add(new Point(currentPoint.x+1,currentPoint.y));
  152.                     queue.add(prevList);
  153.                 }
  154.             }
  155.             if (!matriks[currentPoint.y][currentPoint.x-1]){
  156.                 if(!matriksSudahDikunjungi[currentPoint.y][currentPoint.x-1]){
  157.                     ArrayList<Point> prevList = new ArrayList<Point>();
  158.                     copyList(currentList,prevList);
  159.                     prevList.add(new Point(currentPoint.x-1,currentPoint.y));
  160.                     queue.add(prevList);
  161.                 }
  162.             }
  163.             if (!matriks[currentPoint.y+1][currentPoint.x]){
  164.                 if(!matriksSudahDikunjungi[currentPoint.y+1][currentPoint.x]){
  165.                     ArrayList<Point> prevList = new ArrayList<Point>();
  166.                     copyList(currentList,prevList);
  167.                     prevList.add(new Point(currentPoint.x,currentPoint.y+1));
  168.                     queue.add(prevList);
  169.                 }
  170.             }
  171.             if (!matriks[currentPoint.y-1][currentPoint.x]){
  172.                 if(!matriksSudahDikunjungi[currentPoint.y-1][currentPoint.x]){
  173.                     ArrayList<Point> prevList = new ArrayList<Point>();
  174.                     copyList(currentList,prevList);
  175.                     prevList.add(new Point(currentPoint.x,currentPoint.y-1));
  176.                     queue.add(prevList);
  177.                 }
  178.             }    
  179.             currentList = queue.get(0);
  180.             currentPoint = currentList.get(currentList.size()-1);
  181.             queue.remove(0);
  182.         }
  183.         //currentList yg skr udah jadi tempat terakhirnya
  184.         // char[][] path = new char[baris][kolom];
  185.         // for (int i = 0;i<baris;i++){
  186.         //     for (int j = 0;j<kolom;j++){
  187.         //         if (matriks[i][j]){
  188.         //             path[i][j] = '1';
  189.         //         }else{
  190.         //             path[i][j] = '0';
  191.         //         }
  192.         //     }
  193.         // }
  194.  
  195.         // for (int i = 0;i<currentList.size();i++){
  196.         //     // System.out.println("Titik  adalah : X="+currentList.get(i).x+" Y="+currentList.get(i).y);
  197.         //     path[currentList.get(i).y][currentList.get(i).x] = '-';
  198.         // }
  199.  
  200.         // for (int i = 0;i<baris;i++){
  201.         //     for (int j = 0;j<kolom;j++){
  202.         //         System.out.print(path[i][j]);
  203.         //     }
  204.         //     System.out.println();
  205.         // }
  206.         // System.out.println("Titik akhir adalah : X="+currentPoint.x+" Y="+currentPoint.y);
  207.     }
  208.    
  209.     public Point findFinish(){
  210.         Point pointTemp = new Point();
  211.         boolean found = false;
  212.         int i = 0;
  213.         while ((!found)&&(i<kolom)){
  214.             if (!matriks[0][i]&&((i!=start.x)||(start.y!=0))){
  215.                 pointTemp.x = i;
  216.                 pointTemp.y = 0;
  217.                 found = true;
  218.             }
  219.             if ((!matriks[baris-1][i])&&(!found)&&((i!=start.x)||(start.y!=baris-1))){
  220.                 pointTemp.x = i;
  221.                 pointTemp.y = baris-1;
  222.                 found = true;
  223.             }
  224.             i++;
  225.         }
  226.         i = 0;
  227.         while ((!found)&&(i<baris)){
  228.             if ((!matriks[i][0])&&((0!=start.x)||(start.y!=i))){
  229.                 pointTemp.x = 0;
  230.                 pointTemp.y = i;
  231.                 found = true;
  232.             }
  233.             if ((!matriks[i][kolom-1])&&(!found)&&((kolom-1!=start.x)||(start.y!=i))){
  234.                 pointTemp.x = kolom-1;
  235.                 pointTemp.y = i;
  236.                 found = true;
  237.             }
  238.             i++;
  239.         }
  240.         return pointTemp;
  241.     }
  242.  
  243.     public void solveAStar(){   //Menyelesaikan dengan algoritma A*
  244.         int fh = 0,idxMin;
  245.         currentNode.P.clear();
  246.         boolean[][] matriksSudahDikunjungi = new boolean[baris][kolom];
  247.         Point finishPoint = new Point();
  248.         finishPoint = findFinish();
  249.         ArrayList<Node> arrayNode = new ArrayList<Node>();
  250.         // Node currentNode = new Node();
  251.         currentNode.P.add(new Point(start.x,start.y));
  252.         currentNode.cost = fh + currentNode.P.get(currentNode.P.size()-1).jarakDuaTitik(finishPoint);// Ini adalah fungsi cost-nya
  253.         matriksSudahDikunjungi[currentNode.P.get(currentNode.P.size()-1).y][currentNode.P.get(currentNode.P.size()-1).x] = true;
  254.        
  255.         if (currentNode.P.get(currentNode.P.size()-1).x == 0){
  256.             currentNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x+1,currentNode.P.get(currentNode.P.size()-1).y));
  257.         }
  258.         if (currentNode.P.get(currentNode.P.size()-1).x == kolom-1){
  259.             currentNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x-1,currentNode.P.get(currentNode.P.size()-1).y));
  260.         }
  261.         if (currentNode.P.get(currentNode.P.size()-1).y == 0){
  262.             currentNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x,currentNode.P.get(currentNode.P.size()-1).y+1));
  263.         }
  264.         if (currentNode.P.get(currentNode.P.size()-1).y == baris-1){
  265.             currentNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x,currentNode.P.get(currentNode.P.size()-1).y-1));
  266.         }
  267.  
  268.        
  269.         while ((currentNode.P.get(currentNode.P.size()-1).x!=finishPoint.x)||(currentNode.P.get(currentNode.P.size()-1).y!=finishPoint.y)){
  270.             fh++;
  271.             matriksSudahDikunjungi[currentNode.P.get(currentNode.P.size()-1).y][currentNode.P.get(currentNode.P.size()-1).x] = true;
  272.             if (!matriks[currentNode.P.get(currentNode.P.size()-1).y][currentNode.P.get(currentNode.P.size()-1).x+1]){
  273.                 if(!matriksSudahDikunjungi[currentNode.P.get(currentNode.P.size()-1).y][currentNode.P.get(currentNode.P.size()-1).x+1]){
  274.                     Node nextNode = new Node();
  275.                     nextNode.copyNode(currentNode);
  276.                     nextNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x+1,currentNode.P.get(currentNode.P.size()-1).y));
  277.                     nextNode.cost = fh + nextNode.P.get(currentNode.P.size()-1).jarakDuaTitik(finishPoint);
  278.                     arrayNode.add(nextNode);
  279.                    
  280.                 }
  281.             }
  282.             if (!matriks[currentNode.P.get(currentNode.P.size()-1).y][currentNode.P.get(currentNode.P.size()-1).x-1]){
  283.                 if(!matriksSudahDikunjungi[currentNode.P.get(currentNode.P.size()-1).y][currentNode.P.get(currentNode.P.size()-1).x-1]){
  284.                     Node nextNode = new Node();
  285.                     nextNode.copyNode(currentNode);
  286.                     nextNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x-1,currentNode.P.get(currentNode.P.size()-1).y));
  287.                     nextNode.cost = fh + nextNode.P.get(currentNode.P.size()-1).jarakDuaTitik(finishPoint);
  288.                     arrayNode.add(nextNode);
  289.                    
  290.                 }
  291.             }
  292.             if (!matriks[currentNode.P.get(currentNode.P.size()-1).y+1][currentNode.P.get(currentNode.P.size()-1).x]){
  293.                 if(!matriksSudahDikunjungi[currentNode.P.get(currentNode.P.size()-1).y+1][currentNode.P.get(currentNode.P.size()-1).x]){
  294.                     Node nextNode = new Node();
  295.                     nextNode.copyNode(currentNode);
  296.                     nextNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x,currentNode.P.get(currentNode.P.size()-1).y+1));
  297.                     nextNode.cost = fh + nextNode.P.get(currentNode.P.size()-1).jarakDuaTitik(finishPoint);
  298.                     arrayNode.add(nextNode);
  299.                 }
  300.             }
  301.             if (!matriks[currentNode.P.get(currentNode.P.size()-1).y-1][currentNode.P.get(currentNode.P.size()-1).x]){
  302.                 if(!matriksSudahDikunjungi[currentNode.P.get(currentNode.P.size()-1).y-1][currentNode.P.get(currentNode.P.size()-1).x]){
  303.                     Node nextNode = new Node();
  304.                     nextNode.copyNode(currentNode);
  305.                     nextNode.P.add(new Point(currentNode.P.get(currentNode.P.size()-1).x,currentNode.P.get(currentNode.P.size()-1).y-1));
  306.                     nextNode.cost = fh + nextNode.P.get(currentNode.P.size()-1).jarakDuaTitik(finishPoint);
  307.                     arrayNode.add(nextNode);
  308.                 }
  309.             }
  310.             idxMin = 0;
  311.             for (int i = 1;i<arrayNode.size();i++){
  312.                 if (arrayNode.get(i).cost<arrayNode.get(idxMin).cost){
  313.                     idxMin = i;
  314.                 }
  315.             }
  316.             currentNode = arrayNode.get(idxMin);
  317.             arrayNode.remove(idxMin);
  318.             // System.out.println("X = "+currentNode.P.get(currentNode.P.size()-1).x+" Y= "+currentNode.P.get(currentNode.P.size()-1).y+" Cost = "+currentNode.cost);
  319.         }
  320.  
  321.         currentNode.P.get(currentNode.P.size()-1).print(); //currentNode yg skr ini titik akhirnya
  322.  
  323.         // DI BAWAH INI BUAT NGEPRINT MATRIKSNYA
  324.         char[][] path = new char[baris][kolom];
  325.         for (int i = 0;i<baris;i++){
  326.             for (int j = 0;j<kolom;j++){
  327.                 if (matriks[i][j]){
  328.                     path[i][j] = '1';
  329.                 }else{
  330.                     path[i][j] = '0';
  331.                 }
  332.             }
  333.         }
  334.  
  335.         for (int i = 0;i<currentNode.P.size();i++){
  336.             path[currentNode.P.get(i).y][currentNode.P.get(i).x] = '-';
  337.         }
  338.  
  339.         // for (int i = 0;i<baris;i++){
  340.         //     for (int j = 0;j<kolom;j++){
  341.         //         System.out.print(path[i][j]);
  342.         //     }
  343.         //     System.out.println();
  344.         // }
  345.     }
  346.  
  347.     public static void main(String args[]){
  348.         BufferedReader br = null,br2 = null;
  349.         FileReader fr = null,fr2 = null;
  350.         String namaFile;
  351.         Scanner scan = new Scanner(System.in);
  352.         System.out.print("Input nama file : ");
  353.         namaFile = scan.nextLine();
  354.         scan.close();
  355.         try{
  356.             fr = new FileReader(namaFile);
  357.             br = new BufferedReader(fr);
  358.            
  359.             int x,y,i;
  360.             String sCurrentLine = br.readLine();
  361.             x = sCurrentLine.length();
  362.             y = 0;
  363.             while(sCurrentLine!=null){
  364.                 y++;
  365.                 sCurrentLine = br.readLine();
  366.             }
  367.             System.out.println("Jumlah Baris : "+y);
  368.             System.out.println("Jumlah Kolom : "+x);
  369.             System.out.println();
  370.  
  371.             labirin objLabirin = new labirin(y,x);
  372.  
  373.             fr2 = new FileReader(namaFile);
  374.             br2 = new BufferedReader(fr2);
  375.             y = 0;
  376.             sCurrentLine = br2.readLine();
  377.             while(sCurrentLine!=null){
  378.                 i = 0;
  379.                 while(i<x){
  380.                     if (sCurrentLine.charAt(i)=='0'){
  381.                         objLabirin.matriks[y][i] = false;
  382.                     }else{
  383.                         objLabirin.matriks[y][i] = true;
  384.                     }
  385.                     i++;
  386.                 }
  387.                 y++;
  388.                 sCurrentLine = br2.readLine();
  389.             }
  390.             objLabirin.transferMatriks();
  391.             objLabirin.printLabirin();
  392.             objLabirin.findStart();
  393.             System.out.println();
  394.             // objLabirin.solveBFS();
  395.             System.out.println();
  396.             objLabirin.solveAStar();
  397.         }
  398.         catch (IOException e) {
  399.             e.printStackTrace();
  400.             System.out.println("Ada kesalahan pada file eksternal.");
  401.         }
  402.         finally {
  403.             try {
  404.                 if (br != null)
  405.                     br.close();
  406.                 if (fr != null)
  407.                     fr.close();
  408.             } catch (IOException ex) {
  409.                 ex.printStackTrace();
  410.             }
  411.         }
  412.     }
  413. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!