Source code for submission s742

Go to diff to previous submission

Grasshopper.java

  1.  
  2. import java.io.BufferedReader;
  3.  
  4. /*
  5.  * To change this template, choose Tools | Templates
  6.  * and open the template in the editor.
  7.  */
  8. import java.io.IOException;
  9. import java.io.InputStreamReader;
  10. import java.util.LinkedList;
  11. import java.util.StringTokenizer;
  12.  
  13.  
  14.  
  15. /**
  16.  *
  17.  * @author cteam022
  18.  */
  19. public class Grasshopper {
  20.  
  23.  
  24.     /**
  25.      * @param args the command line arguments
  26.      */
  27.     public static void main(String[] args) throws IOException {
  28.         Grasshopper g = new Grasshopper();
  29.         while(true){g.uloha();}
  30.     }
  31.  
  32.     void uloha() throws IOException{
  33.         if(!input.ready()){System.exit(0);}
  34.         st = new StringTokenizer(input.readLine());
  35.         int a = Integer.valueOf(st.nextToken());
  36.         int b = Integer.valueOf(st.nextToken());
  37.         int x1 = Integer.valueOf(st.nextToken());
  38.         int y1 = Integer.valueOf(st.nextToken());
  39.         int x2 = Integer.valueOf(st.nextToken());
  40.         int y2 = Integer.valueOf(st.nextToken());
  41.  
  42.         int x = x1, y = y1;
  43.  
  44.         int i;
  45.  
  46.         for(i=0; Math.abs(x - x2) > 2 && Math.abs(y - y2)>2; i++){
  47.             int dx = x2 - x;
  48.             int dy = y2 - y;
  49.  
  50.             if(Math.abs(dx) >= Math.abs(dy)){
  51.                 x += Math.signum(dx)*2;
  52.                 y += Math.signum(dy);
  53.             }else{
  54.                 x += Math.signum(dx);
  55.                 y += Math.signum(dy)*2;
  56.             }
  57.         }
  58.  
  59.         LinkedList<Integer[]> fifo = new LinkedList<Integer[]>();
  60.         fifo.addLast(new Integer[]{x, y, 0});
  61.         boolean[][] visited = new boolean[b][a];
  62.         for (int k = 0; k < b; k++)
  63.             for (int l = 0; l < a; l++)
  64.                 visited[k][l] = false;
  65.  
  66.  
  67.         int p = rekurze(6, x2, y2, a, b, visited, fifo);
  68.  
  69.         if(p == -1){
  70.             System.out.println("impossible");
  71.         }else{
  72.             System.out.println(i+p);
  73.         }
  74.  
  75.     }
  76.  
  77.     static int rekurze(int pocet, int x2, int y2, int a, int b, boolean[][] visited, LinkedList<Integer[]> fifo){
  78.         while (!fifo.isEmpty()) {
  79.  
  80.         Integer[] coords = fifo.pop();
  81.         int x = coords[0]; int y = coords[1]; int dep = coords[2];
  82.  
  83.         if (visited[y][x]) continue;
  84.         visited[y][x] = true;
  85.  
  86.         if (x2 == x && y2 == y) return dep;
  87.  
  88.  
  89.  
  90.         for(int druhx = -1; druhx < 2; druhx+=2){           
  91.             for(int druhy = -1; druhy < 2; druhy+=2){
  92.                 if(x+druhx*2 < a && x+druhx*2>=0 && y+druhy < b && y+druhy >=0){
  93.                     fifo.addLast(new Integer[]{x+druhx*2, y+druhy, dep+1});
  94.                 }
  95.                 if(x+druhx < a && x+druhx>=0 && y+druhy*2 < b && y+druhy*2 >=0){
  96.                     fifo.addLast(new Integer[]{x+druhx, y+druhy*2, dep+1});
  97.                 }
  98.             }
  99.  
  100.         }   
  101.         }
  102.  
  103.         return -1;
  104.     }
  105.  
  106. }
  107.  

Diff to submission s680

Grasshopper.java

--- c4.s680.cteam022.grasshop.java.0.Grasshopper.java
+++ c4.s742.cteam022.grasshop.java.0.Grasshopper.java
@@ -8,4 +8,5 @@
 import java.io.IOException;
 import java.io.InputStreamReader;
+import java.util.LinkedList;
 import java.util.StringTokenizer;
 
@@ -56,7 +57,15 @@
         }
         
-        int p = rekurze(6, x2, y2, x, y, a, b);
+        LinkedList<Integer[]> fifo = new LinkedList<Integer[]>();
+        fifo.addLast(new Integer[]{x, y, 0});
+        boolean[][] visited = new boolean[b][a];
+        for (int k = 0; k < b; k++)
+            for (int l = 0; l < a; l++)
+                visited[k][l] = false;
         
-        if(p == 100){
+        
+        int p = rekurze(6, x2, y2, a, b, visited, fifo);
+        
+        if(p == -1){
             System.out.println("impossible");
         }else{
@@ -66,22 +75,31 @@
     }
     
-    static int rekurze(int pocet, int x2, int y2, int x,int y,int a, int b){
-        if (pocet < 0) return 100;
-        if (x2 == x && y2 == y) return 0;
-        int min = 100;
+    static int rekurze(int pocet, int x2, int y2, int a, int b, boolean[][] visited, LinkedList<Integer[]> fifo){
+        while (!fifo.isEmpty()) {
+        
+        Integer[] coords = fifo.pop();
+        int x = coords[0]; int y = coords[1]; int dep = coords[2];
+        
+        if (visited[y][x]) continue;
+        visited[y][x] = true;
+        
+        if (x2 == x && y2 == y) return dep;
+        
+        
+        
         for(int druhx = -1; druhx < 2; druhx+=2){           
             for(int druhy = -1; druhy < 2; druhy+=2){
                 if(x+druhx*2 < a && x+druhx*2>=0 && y+druhy < b && y+druhy >=0){
-                    int r1 = rekurze(pocet - 1, x2, y2, x+druhx*2, y+druhy, a, b); 
-                    min = Math.min(r1, min);
+                    fifo.addLast(new Integer[]{x+druhx*2, y+druhy, dep+1});
                 }
                 if(x+druhx < a && x+druhx>=0 && y+druhy*2 < b && y+druhy*2 >=0){
-                    int r2 = rekurze(pocet - 1,x2, y2, x+druhx, y+druhy*2, a, b); 
-                    min = Math.min(r2, min);
+                    fifo.addLast(new Integer[]{x+druhx, y+druhy*2, dep+1});
                 }
             }
             
         }   
-        return min==100 ? 100 : min + 1;
+        }
+        
+        return -1;
     }