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) {
} else {
if (grid
[i
][j
] == Integer.
MAX_VALUE) { } else {
}
}
}
}
}
/**
* @param args the command line arguments
*/
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();
}
}
}