Go to diff to previous submission
import java.io.BufferedReader; /* * To change this template, choose Tools | Templates * and open the template in the editor. */ import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.StringTokenizer; /** * * @author cteam022 */ public class Grasshopper { /** * @param args the command line arguments */ Grasshopper g = new Grasshopper(); while(true){g.uloha();} } int x = x1, y = y1; int i; int dx = x2 - x; int dy = y2 - y; }else{ } } boolean[][] visited = new boolean[b][a]; for (int k = 0; k < b; k++) for (int l = 0; l < a; l++) visited[k][l] = false; int p = rekurze(6, x2, y2, a, b, visited, fifo); if(p == -1){ }else{ } } static int rekurze(int pocet, int x2, int y2, int a, int b, boolean[][] visited, LinkedList<Integer[]> fifo){ while (!fifo.isEmpty()) { 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){ } if(x+druhx < a && x+druhx>=0 && y+druhy*2 < b && y+druhy*2 >=0){ } } } } return -1; } }
--- 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; }