Source code for submission s936

Grasshop.java

  1. /*
  2.  * To change this template, choose Tools | Templates
  3.  * and open the template in the editor.
  4.  */
  5.  
  6.  
  7. import java.util.LinkedList;
  8. import java.util.List;
  9. import java.util.Scanner;
  10.  
  11.  
  12. /**
  13.  *
  14.  * @author cteam041
  15.  */
  16. public class Grasshop {
  17.  
  18.     /**eam/index.php?submitted=728
  19.      * @param args the command line arguments
  20.      */
  21.     public static void main(String[] args) {
  22.  
  23.         int R, C, Gr, Gc, Lr, Lc;
  24.  
  25.         Scanner sc = new Scanner(System.in);
  26.         while (sc.hasNextInt()) {
  27.             List<Pos> q = new LinkedList<Pos>();
  28.             R = sc.nextInt();
  29.             C = sc.nextInt();
  30.  
  31.             Gr = sc.nextInt()-1;
  32.             Gc = sc.nextInt()-1;
  33.  
  34.             Lr = sc.nextInt()-1;
  35.             Lc = sc.nextInt()-1;
  36.             Pos start = new Pos();
  37.             start.r = Gr;
  38.             start.c = Gc;
  39.             start.iter = 1;
  40.             q.add(start);
  41.  
  42.             int[][] pole = new int[R][C];
  43.             pole[Gc][Gr] = 1;
  44.  
  45.             int iter = 1;
  46.             boolean found = false;
  47.             while (q.size() > 0) {
  48.  
  49.                 Pos k = q.get(0);
  50.                 q.remove(0);
  51.  
  52.                 iter = k.iter;
  53.  
  54.                 if (Lr == k.r && Lc == k.c) {
  55.                     found = true;
  56.                     System.out.println(k.iter-1);
  57.                     break;
  58.                 }
  59.  
  60.                 int i = k.c;
  61.                 int j = k.r;
  62.  
  63.                 int x = i + 2;
  64.                 int y = j + 1;
  65.                 if (x >= 0 && x < C && y >= 0 && y < R) {
  66.                     if (pole[x][y] == 0) {
  67.                         Pos n = new Pos();
  68.                         n.c = x; n.r = y; n.iter = iter+1;
  69.                         q.add(n);
  70.                         pole[x][y]=n.iter;
  71.  
  72.                     }
  73.                 }
  74.  
  75.                 x = i - 2;
  76.                 y = j + 1;
  77.                 if (x >= 0 && x < C && y >= 0 && y < R) {
  78.                     if (pole[x][y] == 0) {
  79.                         Pos n = new Pos();
  80.                         n.c = x; n.r = y; n.iter = iter+1;
  81.                         q.add(n);
  82.                         pole[x][y]=n.iter;
  83.  
  84.                     }
  85.                 }
  86.  
  87.                 x = i - 2;
  88.                 y = j - 1;
  89.                 if (x >= 0 && x < C && y >= 0 && y < R) {
  90.                     if (pole[x][y] == 0) {
  91.                         Pos n = new Pos();
  92.                         n.c = x; n.r = y; n.iter = iter+1;
  93.                         q.add(n);
  94.                         pole[x][y]=n.iter;
  95.  
  96.                     }
  97.                 }
  98.  
  99.                 x = i + 2;
  100.                 y = j - 1;
  101.                 if (x >= 0 && x < C && y >= 0 && y < R) {
  102.                     if (pole[x][y] == 0) {
  103.                         Pos n = new Pos();
  104.                         n.c = x; n.r = y; n.iter = iter+1;
  105.                         q.add(n);
  106.                         pole[x][y]=n.iter;
  107.  
  108.                     }
  109.                 }
  110.  
  111.                 //opacnefound?:"
  112.                 x = i + 1;
  113.                 y = j + 2;
  114.                 if (x >= 0 && x < C && y >= 0 && y < R) {
  115.                    if (pole[x][y] == 0) {
  116.                         Pos n = new Pos();
  117.                         n.c = x; n.r = y; n.iter = iter+1;
  118.                         q.add(n);
  119.                         pole[x][y]=n.iter;
  120.  
  121.                     }
  122.                 }
  123.  
  124.                 x = i - 1;
  125.                 y = j + 2;
  126.                 if (x >= 0 && x < C && y >= 0 && y < R) {
  127.                     if (pole[x][y] == 0) {
  128.                         Pos n = new Pos();
  129.                         n.c = x; n.r = y; n.iter = iter+1;
  130.                         q.add(n);
  131.                         pole[x][y]=n.iter;
  132.  
  133.                     }
  134.                 }
  135.  
  136.                 x = i - 1;
  137.                 y = j - 2;
  138.                 if (x >= 0 && x < C && y >= 0 && y < R) {
  139.                     if (pole[x][y] == 0) {
  140.                         Pos n = new Pos();
  141.                         n.c = x; n.r = y; n.iter = iter+1;
  142.                         q.add(n);
  143.                         pole[x][y]=n.iter;
  144.  
  145.                     }
  146.                 }
  147.  
  148.                 x = i + 1;
  149.                 y = j - 2;
  150.                 if (x >= 0 && x < C && y >= 0 && y < R) {
  151.                     if (pole[x][y] == 0) {
  152.                         Pos n = new Pos();
  153.                         n.c = x; n.r = y; n.iter = iter+1;
  154.                         q.add(n);
  155.                         pole[x][y]=n.iter;
  156.  
  157.                     }
  158.                 }
  159.  
  160.             }
  161.  
  162.             if (!found)
  163.                 System.out.println("impossible");
  164.  
  165.         }
  166.  
  167.     }
  168. }
  169. class Pos {
  170.  
  171.     public int r,  c, iter;
  172. }
  173.