Grasshop.java

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
/*
 * To change this template, choose Tools | Templates and open the template in
 * the editor.
 */
/**
 *
 * @author cteam066
 */
public class Grasshop {
 
    public static boolean inGrid(int[][] grid, int col, int row) {
        return (col >= 0 && col < grid[0].length && row >= 0 && row < grid.length);
    }
 
    public static int markNext(int[][] grid, int col, int row, int hops) {
 
        int count = 0;
        int[] dx = new int[]{1, 2, 2, 1, -1, -2, -2, -1};
        int[] dy = new int[]{-2, -1, 1, 2, 2, 1, -1, -2};
 
        for (int i = 0; i < 8; i++) {
            int col1 = col + dy[i];
            int row1 = row + dx[i];
 
            if (inGrid(grid, col1, row1) && (grid[row1][col1] == 0 || grid[row1][col1] == Integer.MAX_VALUE)) {
                count++;
                grid[row1][col1] = hops;
            }
        }
        return count;
 
 
 
    }
 
    public static void print(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
 
                if (grid[i][j] == -1) {
                    System.out.print("*");
                } else {
 
                    if (grid[i][j] == Integer.MAX_VALUE) {
                        System.out.print("#");
                    } else {
 
                        System.out.print(grid[i][j]);
                    }
                }
            }
            System.out.println("");
 
        }
        System.out.println("");
    }
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String inputLine = br.readLine();
 
        while (inputLine != null) {
 
 
            String[] input = inputLine.split(" ");
 
            int rows = Integer.parseInt(input[0]);
            int cols = Integer.parseInt(input[1]);
            int startR = Integer.parseInt(input[2]) - 1;
            int startC = Integer.parseInt(input[3]) - 1;
            int endR = Integer.parseInt(input[4]) - 1;
            int endC = Integer.parseInt(input[5]) - 1;
 
 
            int[][] grid = new int[rows][cols];
            grid[startR][startC] = -1;
            grid[endR][endC] = Integer.MAX_VALUE;
 
            int hops = 1;
            int marks = markNext(grid, startR, startC, hops);
 
 
            hops++;
            while (grid[endR][endC] == Integer.MAX_VALUE && marks > 0) {
             //   print(grid);
                marks = 0;
 
                for (int i = 0; i < rows; i++) {
                    for (int j = 0; j < cols; j++) {
 
                        if (grid[i][j] == hops - 1) {
                            marks += markNext(grid, i, j, hops);
                        }
                    }
                }
 
                hops++;
            }
 
            //print(grid);
 
            if (marks == 0) {
                System.out.println("impossible");
            } else {
 
                System.out.println(grid[endR][endC]);
            }
 
 
 
 
            inputLine = br.readLine();
        }
 
    }
}