Problem C
Gregory the Grasshopper
Gregory is a grasshopper. His favourite food are clover leafs—he can simply never have enough of them. Whenever he spots such a leaf, he wants to eat it as quickly as possible. Gregory is also lazy, so he wants to move to the leaf with minimal effort. Your task is to help him to find the shortest way to a clover leaf.
For simplicity, we will assume that Gregory lives on a rectangular grid consisting of unit squares. As a grasshopper, he prefers to move by jumping (or, more exactly, hopping) from one square to the other. Each hop takes him to a square that is in the adjacent row or column in one direction, and two columns or rows away in the other direction. So, his hops resemble the moves of a knight on a chessboard.
Input
The input consists of several test cases, at most
Output
For each test case, print one integer number—the minimal number of hops that Gregory needs to reach the square with his beloved delicacy. If it is not possible to reach that square at all, print the word “impossible” instead.
Sample Input 1 | Sample Output 1 |
---|---|
10 10 10 10 1 1 2 2 1 1 1 2 8 8 1 1 1 2 |
6 impossible 3 |