import java.util.*;

/*
 * We need to get all of the keys. We only need to open doors if they prevent
 * us from getting to a key.
 * 
 * - Order the keys and their locations first in the tunnels?
 * - The order of keys is always a to z? Not necessarily.
 * - If we get to a door and we don't have the key to get through it then backtrack
 *   and find the key? Or don't even go there in the first place?
 * - If another key is closer to our current location than going through the
 *   next door then collect the key for shortest path.
 * - Go for all keys in sae direction until we hit a door that
 *   we can't pass then change direction.
 *
 * BFS from current location to next key.
 */

public class Explorer
{
    public Explorer (Map theMap, boolean debug)
    {
        _theMap = theMap;
        _start = _theMap.getEntrance();
        _totalNumnberOfKeys = _theMap.numberOfKeys();
        _states = new ArrayDeque<State>();
        _visited = new Vector<State>();
        _debug = debug;
    }

   /*
    * Algorithm:
    *
    * - initial starting point @
    * - move to find next key
    * - if we hit a door ...
    *      if we have the key, keep going
    *      if we do not have the key, we can't get through the door so we
    *      need to stop going in that direction and find the key.
    * - each time we find a key, reset the starting point and remember
    *   to reset the visited bit in each Node.
    * - keep going until we hit a door or find all keys
    */

    public int findAllKeys ()
    {
        _states.offer(new State(_start, Collections.emptySet(), 0));

        while (_states.size() > 0)
        {
            State state = _states.pop();
            
            if (_state.numberOfKeys() == _totalNumnberOfKeys)
                return state.numberOfSteps();

            for (Coordinate nextPosition : state.getPosition().directions())
            {
                if (_theMap.validPosition(nextPosition))
                    continue;

                char content = _theMap.getContent(nextPosition);

                if (Util.isDoor(content)) && !_state.hasKey(content))
                    continue;

                Set<Character> keys = _state.getKeys();

                if (Util.isKey(content))
                {
                    keys = new HashSet<>(keys);
                    keys.add(content);
                }

                State nextState = new State(nextPosition, keys, _state.numberOfSteps()+1);

                if (!_visited.add(nextState.getIdentifier())
                    continue;

                _states.add(nextState);
            }
        }
        
        return -1;
    }

    private Map _theMap;
    private Coordinate _start;
    private int _totalNumnberOfKeys;
    private ArrayDeque<State> _states;
    private Vector<String> _visited;
    private boolean _debug;
}
@@ -958,19 +958,20 @@
 ector%3CSt
-ate
+ring
 %3E();%0A   
@@ -1652,17 +1652,20 @@
   State 
-s
+theS
 tate = _
@@ -1707,18 +1707,20 @@
     if (
-_s
+theS
 tate.num
@@ -1778,17 +1778,20 @@
  return 
-s
+theS
 tate.num
@@ -1848,17 +1848,20 @@
 ition : 
-s
+theS
 tate.get
@@ -2097,16 +2097,17 @@
 ent)
-)
  && !
-_s
+theS
 tate
@@ -2193,18 +2193,20 @@
  keys = 
-_s
+theS
 tate.get
@@ -2443,18 +2443,20 @@
 , keys, 
-_s
+theS
 tate.num
@@ -2533,16 +2533,17 @@
 ifier())
+)
 %0A       

Update Explorer.java