Source code for submission s765

Grasshop.java

  1. import java.util.Scanner;
  2.  
  3. public class Grasshop {
  4.  
  5. 	static int x;
  6. 	static int y;
  7. 	static int gx;
  8. 	static int gy;
  9. 	static int lx;
  10. 	static int ly;	
  11.  
  12. 	public static void main(String[] args) throws Exception {
  13. 		Scanner sc = new Scanner(System.in);
  14. 		while (sc.hasNextInt()) {
  15.  
  16. 				x = sc.nextInt();
  17. 				y = sc.nextInt();
  18. 				gx = sc.nextInt() - 1;
  19. 				gy = sc.nextInt() - 1;
  20. 				lx = sc.nextInt() - 1;
  21. 				ly = sc.nextInt() - 1;
  22.  
  23.  
  24. 				int[][] map = new int[x][y];
  25. 		                for (int i = 0; i < x; i++) {
  26. 					for (int j = 0; j < y; j++) {
  27. 						map[i][j] = Integer.MAX_VALUE;
  28. 				 	}
  29. 				}
  30. 				map[gx][gy] = 0;
  31.  
  32. 				boolean change = true;
  33. 				while (change) {
  34.  
  35. 					change = false;		
  36. 					for (int i = 0; i < x; i++) {
  37. 						for (int j = 0; j < y; j++) {
  38. 							change = jump(map, i, j) || change;	
  39.  
  40. 						}
  41. 					}	
  42.  
  43. 					if (map[lx][ly] < Integer.MAX_VALUE) {
  44. 						change = false;
  45. 						System.out.println(map[lx][ly]);
  46.  
  47. 					}
  48.  
  49. 					/*
  50. 					for (int j = 0; j < y; j++) {
  51. 						for (int i = 0; i < x; i++) {
  52. 							if (map[i][j] == Integer.MAX_VALUE) {
  53. 								System.out.print(" - ");
  54. 							} else {
  55. 								System.out.print(map[i][j] + "  ");
  56. 							}
  57. 				 		}
  58. 						System.out.println();
  59. 					}
  60. 					System.out.println("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
  61. 					*/
  62.  
  63. 				}
  64. 				if (map[lx][ly] == Integer.MAX_VALUE) {
  65.  					System.out.println("impossible");
  66. 				}
  67.  
  68. 		}
  69. 	}
  70.  
  71. 	public static boolean jump(int[][] map, int a, int b) {
  72. 		int dx = 0;
  73. 		int dy = 0;
  74.  
  75. 		boolean change = false;
  76.  
  77. 		//System.out.println("Solving.....   "  + a + ", " + b) ;
  78.  
  79. 		if (map[a][b] == Integer.MAX_VALUE) {
  80. 			return false;
  81.  
  82. 		}
  83.  
  84.  
  85.  
  86. 		for (int k=0; k < 8; k++) {
  87. 			if (k == 0) {dx = -2; dy = -1;}
  88. 			if (k == 1) {dx = -2; dy = 1;}
  89. 			if (k == 2) {dx = -1; dy = -2;}
  90. 			if (k == 3) {dx = -1; dy = 2;}
  91. 			if (k == 4) {dx = 1; dy = -2;}
  92. 			if (k == 5) {dx = 1; dy = 2;}
  93. 			if (k == 6) {dx = 2; dy = -1;}
  94. 			if (k == 7) {dx = 2; dy = 1;}
  95.  
  96.  
  97. 			int newX = a + dx;
  98. 			int newY = b + dy;
  99. 			if (isValid(newX, newY)) {
  100. 				if (map[a][b] + 1 < map[newX][newY]) {	
  101. 					map[newX][newY] = map[a][b] + 1;
  102. 					//System.out.println(a + ", " + b + " changed ") ;
  103. 					change = true;
  104. 				}	
  105. 			} 
  106.  
  107.  
  108. 		}
  109.  
  110. 		return change;
  111.  
  112. 	}
  113.  
  114. 	public static boolean isValid(int a, int b) {
  115.  
  116. 		boolean valid = (a >= 0 && a < x && b >=0 && b < y);  
  117.  
  118. 		//System.out.println(a + ", " + b + " : " + valid);
  119. 		return valid;	
  120. 	}
  121. }			
  122.  
  123.  
  124.  
  125.