Editorial for Blitzkreig "Lost Zucky"

A nice problem based on choosing a proper method to denote state and then implementing it correctly and efficiently.

Let's first look at the question:

  Problem Statement:

  Zucky wants to find his way out of a maze in minimum possible steps. 
  Zucky knows that he can get lost in the maze if he can't find the exit so 
  he decides to find a way by writing the code first. Now, he knows that 
  there are doors, keys and walls in the maze. Doors and keys can be of four 
  colors Red, Blue, Green, Yellow (RBGY) and red, blue, green, yellow (rbgy) 
  respectively. (Capital letters represent doors, lower case letters 
  represent keys). Every key can open the door of same color as its own. For 
  eg. r can open R, g can open G, etc. No one can get through the walls. 
  Now, being a busy person he can't write all the code. So, he turns to you 
  for help. Your task is to find minimum number of steps in which he can get 
  out of the maze.
  Note: Zucky can move only in horizontal and vertical direction.

  Input:
  The first line contains t, the number of test cases (1 ≤ t ≤ 5).
  The second line contanis two integers R, C (1 ≤ R, C ≤ 100)
  Then R lines follow. Every line contains C characters, which can be
  1) R, B, G, Y - doors,
  2) r, b, g, y - keys,
  3) # - wall,
  4) . - free space,
  5) * - start point,
  6) X - exit

  Output:
  Each line should contain number of steps required if a path exists and 
  "Trapped!" if there is no path.

  Example:

  Input:
  2
  1 10
  *...rRG..X

  2 5
  *gr##
  RG..X

  Output:
  Trapped!
  5

  Please note that there can be multiple exits, multiple keys/doors of the 
  same color, multiple walls, but only one start point. A key once collected 
  can be used to open as many number of doors.

Okay, now, how do we go about solving this?

Firstly, we notice that if we get rid of the RGBYrgby stuff, then all we have is a simple maze to solve (use a BFS on the implicit graph).
However, one can then notice that the coloured keys create nothing new, other than to multiply a factor of 2^4=16 to the number of states (i.e. for each key, whether it is picked up or not also needs to be added to the state). Noticing this, we have a very clear idea of how to implement a BFS on the implicit graph that is formed here. Each node in the graph is a state which contains row number, column number, and which keys have been picked up.

Putting all of this in a pair<pair<int,int>,pair<pair<bool,bool>,pair<bool,bool>>> might be fun to some, but to me, that's just taking it too far.
What I did instead is made a struct that stores the values and wrote hash, unhash functions in order to convert this struct to and from a long long. This makes it easier to use with STL map which I used to store which vertices were already visited.

Here's the state struct and hash,unhash functions:

  typedef long long ll;

  struct state {
    int row, col, r,g,b,y;
  };

  const ll MULT_BASE = 101;

  ll hash(const state &s) {
    ll ret = 0;
    ret *= MULT_BASE; ret += s.row;
    ret *= MULT_BASE; ret += s.col;
    ret *= MULT_BASE; ret += s.r;
    ret *= MULT_BASE; ret += s.g;
    ret *= MULT_BASE; ret += s.b;
    ret *= MULT_BASE; ret += s.y;
    return ret;
  }

  state unhash(ll h) {
    state ret;
    ret.y = h % MULT_BASE; h /= MULT_BASE;
    ret.b = h % MULT_BASE; h /= MULT_BASE;
    ret.g = h % MULT_BASE; h /= MULT_BASE;
    ret.r = h % MULT_BASE; h /= MULT_BASE;
    ret.col = h % MULT_BASE; h /= MULT_BASE;
    ret.row = h % MULT_BASE; h /= MULT_BASE;
    return ret;
  }

The maze itself is quite simply stored in a character array:

  char maze[101][101];
  int R, C;

Now, we have to figure out which states are accessible from where. Also, we want to update the new state if we end up picking up a key.

  bool should_move(const state &o, state &n) {
    if ( n.row < 0 || n.row >= R || n.col < 0 || n.col >= C )
      return false;
    char l = maze[n.row][n.col];
    if ( l == '.' || l == '*' || l == 'X' )
      return true;
    if ( l == '#' )
      return false;
    if ( l == 'r' )
      return (n.r=1,true);
    if ( l == 'g' )
      return (n.g=1,true);
    if ( l == 'b' )
      return (n.b=1,true);
    if ( l == 'y' )
      return (n.y=1,true);
    if ( l == 'R' )
      return (n.r>0);
    if ( l == 'G' )
      return (n.g>0);
    if ( l == 'B' )
      return (n.b>0);
    if ( l == 'Y' )
      return (n.y>0);
  }

Notice the code for picking up the keys. The syntax return (n.y=1,true); uses a very nice but underused feature of C/C++. The comma operator, used in an expression, executes the left side part, followed by the right side part and keeps the right side part for further evaluation. This basically makes the code do n.y=1; return true; but the code is much more cleaner using this comma notation since unnecessary curly braces are removed and also, the code has a smooth uniform look of returns based on conditions.

Now, we can just do a BFS starting from the first location. We exit out of the BFS the moment we find any exit; thus guaranteeing shortest path.

The BFS is implemented quite simply as follows:

  int bfs(int startrow, int startcol) {
  // returns -1 if not possible to exit 

    map<ll,int> dist;
    int ans = -1;
    state startstate;

    startstate.row = startrow; startstate.col = startcol;
    startstate.r = 0; startstate.g = 0;

    startstate.b = 0; startstate.y = 0;

    queue<pair<ll,int> > q;

    q.push(make_pair(hash(startstate),0));

    while (!q.empty()){
      ll curhash = q.front().first;
      state curstate = unhash(curhash), newstate;
      int curdist = q.front().second;
      q.pop();

      if ( dist.count(curhash) != 0 )
        continue;

      dist[curhash] = curdist;

      if ( maze[curstate.row][curstate.col] == 'X' ) {
        ans = curdist;
        break;
      }

      newstate = curstate; newstate.row += 1;
      if ( should_move(curstate,newstate) )
        q.push(make_pair(hash(newstate),curdist+1));

      newstate = curstate; newstate.row -= 1;
      if ( should_move(curstate,newstate) )
        q.push(make_pair(hash(newstate),curdist+1));

      newstate = curstate; newstate.col += 1;
      if ( should_move(curstate,newstate) )
        q.push(make_pair(hash(newstate),curdist+1));

      newstate = curstate; newstate.col -= 1;
      if ( should_move(curstate,newstate) )
        q.push(make_pair(hash(newstate),curdist+1));

    }

    return ans; 

 }

Let's take a look at what's happening in this (pretty long) code. We are keeping a list of distances to visited states in the dist map. As is done in a normal BFS, we push the first vertex into a queue and then start a loop. However, in this case, the distances matter, and so we put an integer tagged along with the state too which will store the distance (distance means number of steps needed to reach that state). As long as the queue is not empty, we keep taking off the front element and we put all its neighbours into the queue whenever the neighbours are accessible. As soon as we reach a final destination (exit) however, we break out of the loop and return out of the function.

All that remains now is to implement the necessary I/O routines and to call the right functions; and there it is - AC!!!

Any doubts/suggestions/criticisms? Please leave your comments below.