Shortest path on a maze with keys and doors

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
#include
#include
#include
#include
#include
#include
#include

using maze_line = std::vector;
using maze = std::vector;
using position = std::pair;
using item_map = std::unordered_map >;

//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

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 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

-
visited_position

std::unordered_map > visited_position;

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

std::unordered_map, 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> visited_position

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

-
Consider something like boost::optional as the return type to more clearly indicate failure.

-
Don't write expressions comparing to booleans:

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

Simply:

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

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

-
"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...

StackExchange Code Review Q#106272, answer score: 6