grasshop.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
 
/**
 *
 * @author cteam040
 */
import java.awt.Point;
import java.util.*;
import java.io.*;
 
public class grasshop {
 
    public static void main(String[] s) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String ln;
        next_case:
        while ((ln = br.readLine()) != null) {
            st = new StringTokenizer(ln);
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            int Gy = Integer.parseInt(st.nextToken());
            int Gx = Integer.parseInt(st.nextToken());
            int Sy = Integer.parseInt(st.nextToken());
            int Sx = Integer.parseInt(st.nextToken());
            Set<Stav> closed = new HashSet<Stav>();
            LinkedList<Stav> open = new LinkedList<Stav>();
            Stav start = new Stav(Sx,Sy,0);
            open.add(start);
            while(!open.isEmpty())
            {
                Stav cur = open.removeFirst();
                if(cur.x==Gx && cur.y==Gy)
                {
                    System.out.println(cur.len);
                    continue next_case;
                }
                if(closed.contains(cur))
                    continue;
                closed.add(cur);
                for(int[] mov:moves)
                {
 
                    Stav nstav = new Stav(cur.x+mov[0],cur.y+mov[1],cur.len+1);
                    if(nstav.x<1 || nstav.y<1 || nstav.x>w || nstav.y>h)
                        continue;
                    open.addLast(nstav);
                }
            }
            System.out.println("impossible");
        }
 
    }
 
    static public int[][] moves  = new int[][]{
        {2,-1},
        {1,-2},
        {-1,-2},
        {-2,-1},
        {-2,1},
        {-1,2},
        {1,2},
        {2,1},
    };
 
    public static class Stav
    {
 
        int x,y;
        int len;
 
        public Stav(int x, int y, int len) {
            this.x = x;
            this.y = y;
            this.len = len;
        }
 
        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Stav other = (Stav) obj;
            if (this.x != other.x) {
                return false;
            }
            if (this.y != other.y) {
                return false;
            }
            return true;
        }
 
        @Override
        public int hashCode() {
            int hash = 5;
            hash = 61 * hash + this.x;
            hash = 61 * hash + this.y;
            return hash;
        }
        public String toString()
        {
            return "{"+x+","+y+","+len+"}";
        }
 
    }
}