Source code for submission s941

Go to diff to previous submission

GrassHop.java

  1. package javaapplication1;
  2.  
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. import java.util.Scanner;
  6.  
  7. public class GrassHop {
  8.  
  9. final static int[][] moves = {
  10. {1, 2},
  11. {-1, 2},
  12. {-1, -2},
  13. {1, -2},
  14. {2, 1},
  15. {-2, 1},
  16. {-2, -1},
  17. {2, -1}};
  18. static boolean[] invalid;
  19. static int n, m;
  20.  
  21. public static void main(String[] args) {
  22. Scanner scanner = new Scanner(System.in);
  23. while (scanner.hasNext()) {
  24. n = scanner.nextInt();
  25. m = scanner.nextInt();
  26.  
  27. invalid = new boolean[n * m];
  28.  
  29. int sy = scanner.nextInt() - 1;
  30. int sx = scanner.nextInt() - 1;
  31.  
  32. int ey = scanner.nextInt() - 1;
  33. int ex = scanner.nextInt() - 1;
  34.  
  35. Queue<Integer> queue = new LinkedList<Integer>();
  36.  
  37. queue.add(sy);
  38. queue.add(sx);
  39. queue.add(0);
  40.  
  41. int steps = -1;
  42.  
  43. while (!queue.isEmpty()) {
  44. int y = queue.poll();
  45. int x = queue.poll();
  46. int t = queue.poll();
  47.  
  48. if (y == ey && x == ex) {
  49. steps = t;
  50. break;
  51. }
  52.  
  53. for (int[] move : moves) {
  54. int ny = y + move[0];
  55. int nx = x + move[1];
  56. if (canGo(ny, nx)) {
  57. queue.add(ny);
  58. queue.add(nx);
  59. queue.add(t + 1);
  60. invalid[ny * m + nx] = true;
  61. }
  62. }
  63. }
  64. if (steps == -1) {
  65. System.out.println("impossible");
  66. } else {
  67. System.out.println(steps);
  68. }
  69. }
  70. }
  71.  
  72. private static boolean canGo(int y, int x) {
  73. if (y >= 0 && y < n && x >= 0 && x < m) {
  74. return !invalid[y * m + x];
  75. }
  76. return false;
  77. }
  78. }
  79.  

Diff to submission s931

GrassHop.java

--- c4.s931.cteam026.grasshop.java.0.GrassHop.java
+++ c4.s941.cteam026.grasshop.java.0.GrassHop.java
@@ -41,5 +41,4 @@
             int steps = -1;
             
-            int i = 0;
             while (!queue.isEmpty()) {
                 int y = queue.poll();
@@ -59,5 +58,5 @@
                         queue.add(nx);
                         queue.add(t + 1);
-                        invalid[ny * n + nx] = true;
+                        invalid[ny * m + nx] = true;
                     }
                 }
@@ -73,5 +72,5 @@
     private static boolean canGo(int y, int x) {
         if (y >= 0 && y < n && x >= 0 && x < m) {
-            return !invalid[y * n + x];
+            return !invalid[y * m + x];
         }
         return false;