Shortest path on a maze with keys and doors

Question

The locks of the doors present in the maze are of 7 types: A, B, C, D, E, F and G. There are also some copies of keys around the maze, which can be of types a, b, c, d, e, f or g. A key of type a opens a door of type A, a key of type b opens a door of type B etc. Once a door is opened with a key, the door remains opened, of course, and you can take the key within to open as many doors as you want (of the key type). In the maze there is exactly one exit.

The input represents the maze and consists of at most 100 lines with at most 100 characters different from end-of-line each, and the number of characters per line is always the same. The character @ identifies the initial position, the character * identifies the exit, the walls of the labyrinth are identified by the character #, the doors by characters in the set {A, …, G}, the keys by characters in the set {a, …, g}, and the other free positions by the character . (dot). The total of characters in the labyrinth different from # and from . is at most 100, and there is exactly one character * and one character @. Moves only in horizontal or vertical directions. The input ends in end-of-file.

For the output print a line containing a single integer, which is meant to represent shortest path to getup from @ to *. If it is not possible to leave the maze, print a line containing only two characters - (hyphen).

To solve this i've tried a BFS with recursion to every key found. (I know the getchar_unlocked, puts and printf aren't good for I/O. But they are faster than cin/cout)

Is there a faster solution ?

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <unordered_map>
#include <queue>
#include <limits>
#include <string>


using maze_line = std::vector<char>;
using maze      = std::vector< maze_line >;
using position  = std::pair<int, int>;
using item_map  = std::unordered_map< char , std::vector< position > >;


//globals
static const position NULLE(-1,-1); //mark the end of a level on BFS
static item_map door_map; //save doors positions
static item_map key_map; //save keys positions

int flood[4][2] = {
    {-1,+0},
    {+1,+0},
    {+0,-1},
    {+0,+1}
};

int DFS(maze &m , position &initial, position &final){
    std::unordered_map< int, std::unordered_map<int, bool> > visited_position;
    
    std::queue<position> qp;
    qp.push(initial);
    qp.push(NULLE);
    
    int path_size_counter = 0;
    int path_size_current = std::numeric_limits<int>::max();
    int path_size_recur   = std::numeric_limits<int>::max(); //best path size in case of recursion
    
    while (!qp.empty()) {
        position p = qp.front();
        qp.pop();
        
        if(p == NULLE){
            ++path_size_counter;
            if(!qp.empty())
                qp.push(NULLE);
            continue;
        }
        
        //invalid position
        if(!(0 <= p.first && p.first < m.size() && 0 <= p.second && p.second < m[0].size())){
            continue;
        }
        
        if(visited_position[p.first][p.second] == true){
            continue;
        }
        
        if(p == final){
            path_size_current = path_size_counter;
            break;
        }
        
        //its not a free path
        if(m[p.first][p.second] != '.'){
            //its a key
            if('a' <= m[p.first][p.second] && m[p.first][p.second] <= 'g'){
                maze copy (m);
                
                char key = m[p.first][p.second];
                
                //get the door that matches the key found
                char door = std::toupper(key);
                
                //open all the doors mateched on the copy maze
                std::vector<position> &posisd = door_map[door];
                for (auto &pos_door : posisd) {
                    copy[pos_door.first][pos_door.second] = '.';
                }
                
                //erase this key from the copy maze
                std::vector<position> &posisk = key_map[key];
                for (auto &pos_key : posisk) {
                    copy[pos_key.first][pos_key.second] = '.';
                }
                
                //get minimum path for a recursion
                int aux = DFS(copy,p,final);
                if(aux != std::numeric_limits<int>::max())
                    path_size_recur = std::min(path_size_recur,path_size_counter + aux); //the path to the key + the path from key to exit
                
            }
            else
                continue;
        }
        
        //here only keys and '.'
        visited_position[p.first][p.second] = true;
        
        for (int i = 0; i < 4; ++i) {
            int x = p.first  + flood[i][0];
            int y = p.second + flood[i][1];
            
            position new_pos(x,y);
            qp.push(new_pos);
        }
        
    }
    
    return std::min(path_size_current, path_size_recur);
}

int main(void){
    maze     m ;
    position initial;
    position final;
    
    char ch;
    for (int i = 0; (ch = getchar_unlocked()) != EOF ; ++i) {
        maze_line l;
        
        for (int j = 0; ch != '\n'; ++j){
            
            if('A' <= ch && ch <= 'G'){ //it's a door
                door_map[ch].push_back(std::make_pair(i, j));
            }
            
            else if ('a' <= ch && ch <= 'g'){
                key_map[ch].push_back(std::make_pair(i, j));
            }
            
            else if(ch == '@'){
                initial = std::make_pair(i, j);
                ch = '.';
            }
            
            else if(ch == '*'){
                final = std::make_pair(i, j);
            }
            
            l.push_back(ch);
            ch = getchar_unlocked();
        }
        
        m.push_back(l);
    }
    
    int dfs = DFS(m, initial, final);
    if(dfs == std::numeric_limits<int>::max())
        puts("--");
    else
        printf("%d\n",dfs);
}

Input sample:

..............
.a##########B.
.#..........#.
.#.########.#.
.#.#......#.#.
.#.#.a##B.#.#.
.#.#.#.@#.#.#.
.C.#.D.#ad#.#.
.#.B.#....#.#.
.#.#.#####A.#.
.###........#.
.#.bA########.
*#..c.........

[email protected]...*

Output sample

35

--

Answer 1

Treatment of Keys

You're doing a whole lot of extra work - both in terms of actual operations and code - the way you're treating keys. You're copying the entire maze everytime you get a key, and doing a whole separate search. That is unnecessary effort.

Consider the canonical breadth-first-search double loop:

while Q is not empty:
    u = Q.dequeue()
    for each node n that is adjacent to u
        stuff

Instead of taking evasive action when we pick up a key, just save that information into our path:

struct Path {
    position pos;
    std::array<bool, 7> keys;
};

That way, the determination of "adjacent to u" can be done as follows: take all the tiles adjacent to our position. Drop the walls. Drop the doors for which we don't have a key. If we step onto a new square that is a key, turn on the appropriate flag in keys.

That simplifies the code dramatically. No exceptional cases - no unnecessary copies or recursion. Now we're back to a normal breadth-first search. This actually has additional benefits in that you don't need your door_map or key_map either.

Add Heuristics

Consider also adding a heuristic to your queue. Rather than simply effectively sorting by path length, we can also add Manhattan distance as a lower bound. This will make our search more focused on the best candidates remaining. This approach is the A* search algorithm.

Code comments

1. visited_position

   std::unordered_map< int, std::unordered_map<int, bool> > visited_position;
   

   is very inefficient as you're now requiring two lookups. This can be simplified to:

   std::unordered_map<std::pair<int, int>, bool> visited_position;
   

   provided you can add a reasonable hash. But even that is completely unnecessary, as you can simply have an appropriately sized:

   std::vector<std::vector<bool>> visited_position
   

2. flood isn't a good name for that variable. Perhaps directions?

3. Consider something like boost::optional<int> as the return type to more clearly indicate failure.

4. Don't write expressions comparing to booleans:

   if(visited_position[p.first][p.second] == true){
   

   Simply:

   if (visited_position[p.first][p.second){
   

5. Your breadth-first search function is named DFS(). That is confusing.

6. "I know the getchar_unlocked, puts and printf aren't good for I/O. But they are faster than cin/cout" I would worry about the performance of your algorithm way before I would worry about the performance of your just receiving input...