Source code for submission s1301

Go to diff to previous submission

Main.java

  1. import java.util.LinkedList;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.  
  6. 	public static final int[][] polePozic={{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};
  7.  
  8. 	public static void main(String[] args) {
  9. 		Scanner sc=new Scanner(System.in);
  10. 		while(sc.hasNext()){
  11.  
  12. 			int pocetRadek=sc.nextInt();
  13. 			int pocetSloupcu=sc.nextInt();
  14.  
  15. 			int poziceSkokanaX=sc.nextInt();
  16. 			int poziceSkokanaY=sc.nextInt();
  17. 			int poziceMnamkyX=sc.nextInt();
  18. 			int poziceMnamkyY=sc.nextInt();
  19.  
  20. 			int poleJizSkakano[][]=new int[pocetRadek+1][pocetSloupcu+1];
  21. 			for(int i=0;i<pocetRadek;i++){
  22. 				for(int j=0;j<pocetSloupcu;j++){
  23. 					poleJizSkakano[i][j]=-1;
  24. 				}
  25. 			}
  26.  
  27. 			poleJizSkakano[poziceSkokanaY][poziceSkokanaX]=0;
  28. 			//			System.out.println(poleJizSkakano[5][5]);
  29. 			LinkedList<Integer> fronta = new LinkedList<Integer>();
  30. 			fronta.add(poziceSkokanaX);
  31. 			fronta.add(poziceSkokanaY);
  32.  
  33. 			boolean nalez=false;
  34. 			while(!fronta.isEmpty() && !nalez){
  35. 				Integer aktX=fronta.get(0); fronta.remove(0);
  36. 				Integer aktY=fronta.get(0); fronta.remove(0);
  37. 				Integer aktStep=poleJizSkakano[aktY][aktX];
  38. //				System.out.println("aktx je "+aktX+"akty je "+aktY+" aktStep je "+aktStep);
  39.  
  40. 				if((aktX ==poziceMnamkyX) && (aktY==poziceMnamkyY)){
  41. 					System.out.println(aktStep);
  42. 					nalez=true;
  43. 				}else{
  44. 					aktStep++;
  45. 					for(int i=0;i<polePozic.length;i++){
  46. 						int testX=aktX+polePozic[i][0];
  47. 						int testY=aktY+polePozic[i][1];
  48.  
  49. 						if(((testX>=1) && (testX<=pocetSloupcu))&&((testY>=1)&&(testY<=pocetRadek))){
  50. 							if(poleJizSkakano[testY][testX]<=0){
  51. 								fronta.add(testX);
  52. 								fronta.add(testY);
  53. 								poleJizSkakano[testY][testX]=aktStep;
  54. 							}
  55. 						}	
  56. 					}
  57. 				}
  58. 			}
  59. //						System.out.println("dostalo se k ifu");
  60. 			if(fronta.isEmpty() && !nalez){
  61. 				System.out.println("impossible");
  62. 			}
  63. 		}
  64. 	}
  65. }
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  

Diff to submission s1200

Main.java

--- c4.s1200.cteam117.grasshop.java.0.Main.java
+++ c4.s1301.cteam117.grasshop.java.0.Main.java
@@ -1,3 +1,3 @@
-import java.util.ArrayList;
+import java.util.LinkedList;
 import java.util.Scanner;
 
@@ -18,11 +18,16 @@
                         int poziceMnamkyY=sc.nextInt();
 
-                        boolean poleJizSkakano[][]=new boolean[pocetRadek+1][pocetSloupcu+1];
-                        poleJizSkakano[poziceSkokanaY][poziceSkokanaX]=true;
+                        int poleJizSkakano[][]=new int[pocetRadek+1][pocetSloupcu+1];
+                        for(int i=0;i<pocetRadek;i++){
+                                for(int j=0;j<pocetSloupcu;j++){
+                                        poleJizSkakano[i][j]=-1;
+                                }
+                        }
+                        
+                        poleJizSkakano[poziceSkokanaY][poziceSkokanaX]=0;
                         //                      System.out.println(poleJizSkakano[5][5]);
-                        ArrayList<Integer> fronta = new ArrayList<Integer>();
+                        LinkedList<Integer> fronta = new LinkedList<Integer>();
                         fronta.add(poziceSkokanaX);
                         fronta.add(poziceSkokanaY);
-                        fronta.add(0);
 
                         boolean nalez=false;
@@ -30,5 +35,5 @@
                                 Integer aktX=fronta.get(0); fronta.remove(0);
                                 Integer aktY=fronta.get(0); fronta.remove(0);
-                                Integer aktStep=fronta.get(0); fronta.remove(0);
+                                Integer aktStep=poleJizSkakano[aktY][aktX];
 //                              System.out.println("aktx je "+aktX+"akty je "+aktY+" aktStep je "+aktStep);
 
@@ -43,8 +48,8 @@
 
                                                 if(((testX>=1) && (testX<=pocetSloupcu))&&((testY>=1)&&(testY<=pocetRadek))){
-                                                        if(!poleJizSkakano[testY][testX]){
+                                                        if(poleJizSkakano[testY][testX]<=0){
                                                                 fronta.add(testX);
                                                                 fronta.add(testY);
-                                                                fronta.add(aktStep);                    
+                                                                poleJizSkakano[testY][testX]=aktStep;
                                                         }
                                                 }       
@@ -54,5 +58,5 @@
                         }
 //                                              System.out.println("dostalo se k ifu");
-                        if(fronta.isEmpty()){
+                        if(fronta.isEmpty() && !nalez){
                                 System.out.println("impossible");
                         }
@@ -62,16 +66,4 @@
 
 
-//      private class Place{
-//              public int x;
-//              public int y;
-//              public int step;
-//
-//              public Place(int x, int y, int step){
-//                      this.x=x;
-//                      this.y=y;
-//                      this.step=step;
-//              }
-//      }
-