GrassHop.java

package javaapplication1;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class GrassHop {
 
    final static int[][] moves = {
        {1, 2},
        {-1, 2},
        {-1, -2},
        {1, -2},
        {2, 1},
        {-2, 1},
        {-2, -1},
        {2, -1}};
    static boolean[] invalid;
    static int n,  m;
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            n = scanner.nextInt();
            m = scanner.nextInt();
 
            invalid = new boolean[n * m];
 
            int sy = scanner.nextInt() - 1;
            int sx = scanner.nextInt() - 1;
 
            int ey = scanner.nextInt() - 1;
            int ex = scanner.nextInt() - 1;
 
            Queue<Integer> queue = new LinkedList<Integer>();
 
            queue.add(sy);
            queue.add(sx);
            queue.add(0);
 
            int steps = -1;
 
            while (!queue.isEmpty()) {
                int y = queue.poll();
                int x = queue.poll();
                int t = queue.poll();
 
                if (y == ey && x == ex) {
                    steps = t;
                    break;
                }
 
                for (int[] move : moves) {
                    int ny = y + move[0];
                    int nx = x + move[1];
                    if (canGo(ny, nx)) {
                        queue.add(ny);
                        queue.add(nx);
                        queue.add(t + 1);
                    }
                }
 
                invalid[y * n + x] = true;
            }
            if (steps == -1) {
                System.out.println("impossible");
            } else {
                System.out.println(steps);
            }
        }
    }
 
    private static boolean canGo(int y, int x) {
        if (y >= 0 && y < n && x >= 0 && x < m) {
            return !invalid[y * n + x];
        }
        return false;
    }
}