(UVA) Knight Moves - Solução 2

You can see another solution for this problem here.

The difference between the solution mentioned above and this new one is that, for this case, I do not use the adjacency list. Then, I have changed the Breadth-First Search method. Now, I only look for the "reachable nodes" when I am in this method.

Comparing the run time between the two solutions:
- The first one ran in: 0.462s.
- The second one ran in: 0.365s.

The solution from 2014 ran in 0.612s.


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

class Main  {
    public static final int MAX = 8;
       
    public static int bfs(int startR, int startC, int goalR, int goalC) {
        int[] vi = {2,2,-2,-2,1,1,-1,-1};
        int[] vj = {1,-1,1,-1,2,-2,2,-2};
       
        Queue<Element> queue = new ArrayDeque<Element>();
        Element e = new Element(startR, startC, 0);
        queue.add(e);
       
        HashSet<Integer> addedToQueue = new HashSet<Integer>();
        addedToQueue.add(startR*MAX+startC);
       
        while (queue.size() > 0) {
            int currPosR = queue.element().posR;
            int currPosC = queue.element().posC;

            if (currPosR == goalR && currPosC == goalC) {
                return queue.element().distance;
            }
           
            for (int k = 0; k < 8; k++) {
                if (currPosR+vi[k] >= 0 && currPosR+vi[k] < MAX && currPosC+vj[k] >= 0 && currPosC+vj[k] < MAX && !addedToQueue.contains((currPosR+vi[k])*MAX+(currPosC+vj[k]))) { // if the position is valid
                    e = new Element(currPosR+vi[k], currPosC+vj[k], queue.element().distance+1);
                    queue.add(e);
                    addedToQueue.add((currPosR+vi[k])*MAX+(currPosC+vj[k]));
                }
            }

            queue.remove();
        }
  
        return -1;
    }
   
    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 sourceIntR = (source.charAt(0)-'a');
            int sourceIntC = (source.charAt(1)-'1');
            int destIntR = (dest.charAt(0)-'a');
            int destIntC = (dest.charAt(1)-'1');
           
            System.out.println("To get from " + source + " to " + dest + " takes " + bfs(sourceIntR, sourceIntC, destIntR, destIntC) + " knight moves.");        
        }    
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

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