(UVA) Knight Moves - Solução 1

If you want to see another solution developed in 2014, click here.

import java.io.*;
import java.util.*;

class Main  {
    public static final int MAX = 8;
    public static HashMap<Integer, ArrayList<Integer>> adjList = new HashMap<Integer, ArrayList<Integer>>();
  
    public static int bfs(int start, int goal) {
        Queue<Element> queue = new ArrayDeque<Element>();
        Element e = new Element(start, 0);
        queue.add(e);
      
        HashSet<Integer> addedToQueue = new HashSet<Integer>();
        addedToQueue.add(start);
      
        while (queue.size() > 0) {
            int currPos = queue.element().pos;

            if (currPos == goal) {
                return queue.element().distance;
            }
          
            ArrayList<Integer> reachable = adjList.get(currPos);
            for (int i = 0; i < reachable.size(); i++) {
                if (!addedToQueue.contains(reachable.get(i))) {
                    e = new Element(reachable.get(i), queue.element().distance+1);
                    queue.add(e);
                    addedToQueue.add(reachable.get(i));
                }
            }
          
            queue.remove();
        }
 
        return -1;
    }
  
    public static void fillAdjList() {
        int[] vi = {2,2,-2,-2,1,1,-1,-1};
        int[] vj = {1,-1,1,-1,2,-2,2,-2};
      
        for (int i = 0; i < MAX; i++) {
            for (int j = 0; j < MAX; j++) {
                int currElement = i*MAX+j; // I am going to get all the elements that are reachable from my current element
                for (int k = 0; k < MAX; k++) {
                    if (i+vi[k] >= 0 && i+vi[k] < MAX && j+vj[k] >= 0 && j+vj[k] < MAX) { // if the position is valid
                        adjList.get(currElement).add((i+vi[k])*MAX+(j+vj[k]));
                    }
                }
            }
        }
    }
  
    public static void initAdjList() {
        for (int i = 0; i < MAX; i++) {
            for (int j = 0; j < MAX; j++) {
                ArrayList<Integer> list = new ArrayList<Integer>();
                int currElement = i*MAX+j;
                adjList.put(currElement, list);
            }
        }
    }
  
    public static void process() throws NumberFormatException, IOException {  
        Scanner sc = new Scanner(System.in);
      
        while (sc.hasNext()) {
            String source = sc.next();
            String dest = sc.next();
          
            int sourceInt = (source.charAt(0)-'a') + (source.charAt(1)-'0'-1)*MAX;
            int destInt = (dest.charAt(0)-'a') + (dest.charAt(1)-'0'-1)*MAX;
          
            initAdjList();
          
            fillAdjList();

            System.out.println("To get from " + source + " to " + dest + " takes " + bfs(sourceInt, destInt) + " knight moves.");       
          
            adjList.clear();
        }   
      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Element {
    int pos;
    int distance;
  
    public Element(int pos, int distance) {
        this.pos = pos;
        this.distance = distance;
    }
}