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>();
        _allStates = 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 ()
    {
        System.out.println("starting at "+_start);

        _states.offer(new State(_start, Collections.emptySet(), 0));

        while (_states.size() > 0)
        {
            System.out.println("states size "+_states.size());

            State theState = _states.pop();
            
            System.out.println("totalKeys "+_totalNumnberOfKeys);
            System.out.println("State keys "+theState.numberOfKeys());

            if (theState.numberOfKeys() == _totalNumnberOfKeys)
                return theState.numberOfSteps();

            for (Coordinate nextPosition : theState.getPosition().directions())
            {
                System.out.println("nextPosition "+nextPosition);

                if (!_theMap.validPosition(nextPosition))
                {
                    System.out.println(nextPosition+" is invalid");
                    continue;
                }

                System.out.println("valid");

                char content = _theMap.getContent(nextPosition);

                System.out.println("content "+content);

                if (Util.isDoor(content) && !theState.hasKey(content))
                {
                    System.out.println("Is a door and we don't have the key!");
                    continue;
                }

                System.out.println("here");

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

                if (Util.isKey(content))
                {
                    System.out.println("is key");

                    keys = new HashSet<Character>(keys);
                    keys.add(content);
                }

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

                System.out.println("nextState "+nextState);

                if (_allStates.contains(nextState))
                {
                    System.out.println("already added");
                    continue;
                }
                else
                    _allStates.add(nextState);

                System.out.println("there");

                _states.add(nextState);

                System.out.println("Adding state "+nextState);
            }

            System.out.println("State sizes here "+ _states.size());
        }
        
        System.out.println("No route found!!");

        return -1;
    }

    private Map _theMap;
    private Coordinate _start;
    private int _totalNumnberOfKeys;
    private ArrayDeque<State> _states;
    private Vector<State> _allStates;
    private boolean _debug;
}
@@ -2241,17 +2241,16 @@
     if (
-!
 _theMap.
@@ -2339,121 +2339,8 @@
 tln(
-nextPosition+%22 is invalid%22);%0A                    continue;%0A                %7D%0A%0A                System.out.println(
 %22val
@@ -2342,24 +2342,28 @@
 (%22valid%22);%0A%0A
+    
             
@@ -2424,32 +2424,36 @@
                 
+  
+  
 System.out.print
@@ -2473,24 +2473,28 @@
 +content);%0A%0A
+    
             
@@ -2560,34 +2560,42 @@
                 
+ 
-%7B%0A
+   %7B%0A    
                 
@@ -2670,32 +2670,36 @@
                 
+    
 continue;%0A      
@@ -2684,32 +2684,36 @@
       continue;%0A
+    
                 
@@ -2723,32 +2723,36 @@
                 
+    
 System.out.print
@@ -2756,32 +2756,36 @@
 intln(%22here%22);%0A%0A
+    
                 
@@ -2835,32 +2835,36 @@
                 
+    
 if (Util.isKey(c
@@ -2880,34 +2880,42 @@
                 
+   
+ 
 %7B%0A
+    
                 
@@ -2965,24 +2965,28 @@
             
+   
+ 
 keys = new H
@@ -3026,24 +3026,28 @@
             
+    
 keys.add(con
@@ -3061,35 +3061,43 @@
                 
+  
+  
 %7D%0A%0A
+    
                 
@@ -3182,32 +3182,36 @@
                 
+    
 System.out.print
@@ -3231,32 +3231,36 @@
  %22+nextState);%0A%0A
+    
                 
@@ -3263,16 +3263,17 @@
     if (
+!
 _allStat
@@ -3304,34 +3304,94 @@
                 
+    
 %7B%0A
+                        _allStates.add(nextState);%0A%0A    
                 
@@ -3418,25 +3418,18 @@
 ln(%22
-already added
+there
 %22);%0A
+%0A
     
@@ -3440,34 +3440,53 @@
             
-continue
+    _states.add(nextState)
 ;%0A
+%0A
             
@@ -3481,34 +3481,91 @@
                 
-%7D%0A
+        System.out.println(%22Adding state %22+nextState);%0A    
                 
@@ -3568,12 +3568,9 @@
     
-else
+%7D
 %0A   
@@ -3590,36 +3590,21 @@
     
-_allStates.add(nextState);%0A%0A
+else%0A        
     
@@ -3639,59 +3639,68 @@
 ln(%22
-there%22);%0A%0A                _states.add(nextState);%0A%0A
+already added%22);%0A                %7D%0A                else%0A    
     
@@ -3734,33 +3734,34 @@
 tln(
-%22Adding state %22+nextState
+nextPosition+%22 is invalid%22
 );%0A 

Update Explorer.java