Go to diff to previous submission
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.LinkedList; public class Grasshop { private static int [][] pole; private static int x0, y0; String str; LinkedList<Boda> list = new LinkedList<Boda>(); int gx,gy,lx,ly; while((str = br.readLine()) != null){ radek = str.split(" "); pole = new int [x0][y0]; Boda b = new Boda(gx-1, gy-1, 1); list.clear(); list.addLast(b); int vzdal = -1; do { Boda a = list.getFirst(); list.removeFirst(); int x = a.x; int y = a.y; if (x == lx-1 && y == ly-1) { vzdal = a.v-1; break; } if (isValid(x+1, y+2)) { list.addLast(new Boda(x+1, y+2, a.v+1)); pole[x+1][y+2] = a.v+1; } if (isValid(x+1, y-2)) { list.addLast(new Boda(x+1, y-2, a.v+1)); pole[x+1][y-2] = a.v+1; } if (isValid(x-1, y+2)) { list.addLast(new Boda(x-1, y+2, a.v+1)); pole[x-1][y+2] = a.v+1; } if (isValid(x-1, y-2)) { list.addLast(new Boda(x-1, y-2, a.v+1)); pole[x-1][y-2] = a.v+1; } if (isValid(x+2, y+1)) { list.addLast(new Boda(x+2, y+1, a.v+1)); pole[x+2][y+1] = a.v+1; } if (isValid(x+2, y-1)) { list.addLast(new Boda(x+2, y-1, a.v+1)); pole[x+2][y-1] = a.v+1; } if (isValid(x-2, y+1)) { list.addLast(new Boda(x-2, y+1, a.v+1)); pole[x-2][y+1] = a.v+1; } if (isValid(x-2, y-1)) { list.addLast(new Boda(x-2, y-1, a.v+1)); pole[x-2][y-1] = a.v+1; } } while(!list.isEmpty()); } } private static boolean isValid(int x, int y) { return x >= 0 && x < x0 && y >= 0 && y < y0 && pole[x][y] == 0; } } class Boda { public int x; public int y; public int v; public Boda(int x, int y, int v) { this.x = x; this.y = y; this.v = v; } }
--- c4.s766.cteam115.grasshop.java.0.Grasshop.java +++ c4.s997.cteam115.grasshop.java.0.Grasshop.java @@ -2,4 +2,6 @@ import java.io.IOException; import java.io.InputStreamReader; +import java.util.HashSet; +import java.util.LinkedList; @@ -7,14 +9,16 @@ private static int [][] pole; + private static int x0, y0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str; String[] radek; - int x,y,gx,gy,lx,ly; + LinkedList<Boda> list = new LinkedList<Boda>(); + int gx,gy,lx,ly; while((str = br.readLine()) != null){ radek = str.split(" "); - x = Integer.parseInt(radek[0]); - y = Integer.parseInt(radek[1]); + x0 = Integer.parseInt(radek[0]); + y0 = Integer.parseInt(radek[1]); gx = Integer.parseInt(radek[2]); gy = Integer.parseInt(radek[3]); @@ -22,44 +26,97 @@ ly = Integer.parseInt(radek[5]); - pole = new int [x][y]; + pole = new int [x0][y0]; - rek(gx-1, gy-1, 1); - System.out.println(pole[lx-1][ly-1] == 0 ? "impossible" : pole[lx-1][ly-1]-1); + Boda b = new Boda(gx-1, gy-1, 1); + list.clear(); + list.addLast(b); + + int vzdal = -1; + do + { + Boda a = list.getFirst(); + list.removeFirst(); + int x = a.x; + int y = a.y; + + if (x == lx-1 && y == ly-1) + { + vzdal = a.v-1; + break; + } + + if (isValid(x+1, y+2)) + { + list.addLast(new Boda(x+1, y+2, a.v+1)); + pole[x+1][y+2] = a.v+1; + } + if (isValid(x+1, y-2)) + { + list.addLast(new Boda(x+1, y-2, a.v+1)); + pole[x+1][y-2] = a.v+1; + } + if (isValid(x-1, y+2)) + { + list.addLast(new Boda(x-1, y+2, a.v+1)); + pole[x-1][y+2] = a.v+1; + } + if (isValid(x-1, y-2)) + { + list.addLast(new Boda(x-1, y-2, a.v+1)); + pole[x-1][y-2] = a.v+1; + } + if (isValid(x+2, y+1)) + { + list.addLast(new Boda(x+2, y+1, a.v+1)); + pole[x+2][y+1] = a.v+1; + } + if (isValid(x+2, y-1)) + { + list.addLast(new Boda(x+2, y-1, a.v+1)); + pole[x+2][y-1] = a.v+1; + } + if (isValid(x-2, y+1)) + { + list.addLast(new Boda(x-2, y+1, a.v+1)); + pole[x-2][y+1] = a.v+1; + } + if (isValid(x-2, y-1)) + { + list.addLast(new Boda(x-2, y-1, a.v+1)); + pole[x-2][y-1] = a.v+1; + } + + } while(!list.isEmpty()); + + + + System.out.println(vzdal == -1 ? "impossible" : vzdal); } } - private static void rek(int x, int y, int cena) - { - if (pole[x][y] == 0 || pole[x][y] > cena) - pole[x][y] = cena; - else - return; - //System.out.println(x+" "+y+" "+cena); - if (isValid(x+1, y+2)) - rek(x+1, y+2, cena+1); - if (isValid(x+1, y-2)) - rek(x+1, y-2, cena+1); - if (isValid(x-1, y+2)) - rek(x-1, y+2, cena+1); - if (isValid(x-1, y-2)) - rek(x-1, y-2, cena+1); - if (isValid(x+2, y+1)) - rek(x+2, y+1, cena+1); - if (isValid(x+2, y-1)) - rek(x+2, y-1, cena+1); - if (isValid(x-2, y+1)) - rek(x-2, y+1, cena+1); - if (isValid(x-2, y-1)) - rek(x-2, y-1, cena+1); - } - private static boolean isValid(int x, int y) { - return x >= 0 && - x < pole.length && + return x >= 0 && + x < x0 && y >= 0 && - y < pole[0].length; + y < y0 && + pole[x][y] == 0; } } + + +class Boda +{ + public int x; + public int y; + public int v; + + public Boda(int x, int y, int v) + { + this.x = x; + this.y = y; + this.v = v; + } +} \ No newline at end of file