Source code for submission s635

Grasshop.java

  1. import java.util.*;
  2. import java.math.*;
  3. import java.io.*;
  4. import java.text.*;
  5.  
  6.  
  7. public class Grasshop {
  9.     static String line, newline;
  10.  
  11.     static int xspan, yspan, pos, x0, y0, xt, yt, steps;
  12.     static StringTokenizer st;
  13.  
  14.     static ArrayList<int[]> nodes = new ArrayList<int[]>();
  15.     static ArrayList<int[]> newnodes = new ArrayList<int[]>();
  16.  
  17.     static boolean[][] visited = new boolean[101][101];
  18.     static boolean foundEnd = false;
  19.  
  20.     static void examineOutnodes(int x, int y){
  21.         int xnew, ynew;
  22.  
  23.         // A 
  24.         xnew = x-2; 
  25.         ynew = y+1;
  26.         if(valid(xnew,ynew) && !visited[xnew][ynew]){
  27.             newnodes.add(new int[]{xnew,ynew});
  28.             visited[xnew][ynew]=true;
  29.             if(xnew==xt && ynew==yt) {
  30.                 foundEnd=true;
  31.                 return;
  32.             }
  33.         }
  34.         // A
  35.         xnew = x+2; 
  36.         ynew = y+1;
  37.         if(valid(xnew,ynew) && !visited[xnew][ynew]){
  38.             newnodes.add(new int[]{xnew,ynew});
  39.             visited[xnew][ynew]=true;
  40.             if(xnew==xt && ynew==yt) {
  41.                 foundEnd=true;
  42.                 return;
  43.             }
  44.         }        
  45.         // B
  46.         xnew = x-2; 
  47.         ynew = y-1;
  48.         if(valid(xnew,ynew) && !visited[xnew][ynew]){
  49.             newnodes.add(new int[]{xnew,ynew});
  50.             visited[xnew][ynew]=true;
  51.             if(xnew==xt && ynew==yt) {
  52.                 foundEnd=true;
  53.                 return;
  54.             }
  55.         } 
  56.         // B
  57.         xnew = x+2; 
  58.         ynew = y-1;
  59.         if(valid(xnew,ynew) && !visited[xnew][ynew]){
  60.             newnodes.add(new int[]{xnew,ynew});
  61.             visited[xnew][ynew]=true;
  62.             if(xnew==xt && ynew==yt) {
  63.                 foundEnd=true;
  64.                 return;
  65.             }
  66.         }  
  67.         // C
  68.         xnew = x-1; 
  69.         ynew = y+2;
  70.         if(valid(xnew,ynew) && !visited[xnew][ynew]){
  71.             newnodes.add(new int[]{xnew,ynew});
  72.             visited[xnew][ynew]=true;
  73.             if(xnew==xt && ynew==yt) {
  74.                 foundEnd=true;
  75.                 return;
  76.             }
  77.         }  
  78.         // C
  79.         xnew = x-1; 
  80.         ynew = y-2;
  81.         if(valid(xnew,ynew) && !visited[xnew][ynew]){
  82.             newnodes.add(new int[]{xnew,ynew});
  83.             visited[xnew][ynew]=true;
  84.             if(xnew==xt && ynew==yt) {
  85.                 foundEnd=true;
  86.                 return;
  87.             }
  88.         } 
  89.         // D
  90.         xnew = x+1; 
  91.         ynew = y+2;
  92.         if(valid(xnew,ynew) && !visited[xnew][ynew]){
  93.             newnodes.add(new int[]{xnew,ynew});
  94.             visited[xnew][ynew]=true;
  95.             if(xnew==xt && ynew==yt) {
  96.                 foundEnd=true;
  97.                 return;
  98.             }
  99.         }
  100.         // D
  101.         xnew = x+1; 
  102.         ynew = y-2;
  103.         if(valid(xnew,ynew) && !visited[xnew][ynew]){
  104.             newnodes.add(new int[]{xnew,ynew});
  105.             visited[xnew][ynew]=true;
  106.             if(xnew==xt && ynew==yt) {
  107.                 foundEnd=true;
  108.                 return;
  109.             }
  110.         }        
  111.     }
  112.  
  113.     static void findWay(){
  114.         nodes.clear();
  115.         newnodes.clear();
  116.         // end == start
  117.         if(xt==x0 && yt==y0){
  118.             steps=0;
  119.             return;
  120.         }
  121.  
  122.         if(!valid(xt,yt) || !valid(x0,y0)){
  123.             steps=-1;
  124.             return;
  125.         }
  126.  
  127.  
  128.         visited[x0][y0] = true;
  129.         nodes.add(new int[]{x0,y0});
  130.  
  131.         while(foundEnd==false && !nodes.isEmpty()){
  132.             steps++;
  133.             for(int[] node : nodes){
  134.                 examineOutnodes(node[0],node[1]);
  135.             }
  136.             nodes.clear();
  137.             nodes.addAll(newnodes);
  138.             newnodes.clear();
  139.         }
  140.  
  141.         if(!foundEnd) steps=-1;
  142.         return;
  143.  
  144.     }
  145.  
  146.     static boolean valid(int x, int y){
  147.         return (x>=1 && x<=xspan && y>=1 && y<=yspan);
  148.     }
  149.     /**
  150.      * @param args the command line arguments
  151.      */
  152.     public static void main(String[] args) throws Exception{
  153.         while( (line=br.readLine()) != null) {
  154.             st = new StringTokenizer(line);
  155.             xspan = Integer.valueOf(st.nextToken());
  156.             yspan = Integer.valueOf(st.nextToken());
  157.             x0 = Integer.valueOf(st.nextToken());
  158.             y0 = Integer.valueOf(st.nextToken());
  159.             xt = Integer.valueOf(st.nextToken());
  160.             yt = Integer.valueOf(st.nextToken());
  161.  
  162.             // nulovani
  163.             for(int xi=1;xi<=xspan;xi++){
  164.                 for(int yi=1;yi<yspan;yi++){
  165.                     visited[xi][yi] = false;
  166.                 }
  167.             }
  168.             foundEnd = false;
  169.             steps = 0;
  170.  
  171.             findWay();
  172.             if(steps==-1)
  173.                 System.out.println("impossible");
  174.             else
  175.                 System.out.println(steps);
  176.  
  177.  
  178.  
  179.         }
  180.  
  181.  
  182.     }
  183.  
  184. }
  185.