title: Codility: PrisonEscape Solution
body: <p>I've recently solved <strong>PrisonEscape</strong> challenge on <strong>Codility</strong>. 
  <a href="https://codility.com/programmers/challenges/phosphorus2014" rel="nofollow">Phosphorus</a></p>
  
  <p>I got <em>33/100</em>. To my opinion my code was covering all of the corner cases. Unfortunately it didn't. </p>
  
  <p>Let me explain my solution.</p>
  
  <p>I've created a graph on an array length of N+1. I've find all the leaves and added them to a queue as a possible guard location. Then I explored through those Nodes. </p>
  
  <p>I've added my ode below. I hope someone can spend their precious time to help me. Thanks.</p>
  
  <pre><code>#include &lt;queue&gt;
  
  struct Node{
      vector&lt;int&gt; neighbours;
      bool hasPrisoner;
      bool guardPlaced;
      bool isVisited;
      unsigned int index;
      Node(): hasPrisoner(false), guardPlaced(false),isVisited(false),index(0)
      {
      }
  };
  
  
  bool shouldBeGuarded(vector&lt;Node&gt;&amp; intersections, int index, int callerIndex)
  {
  
      if(intersections[index].hasPrisoner)
      {
          return true;
      }
      else if(intersections[index].guardPlaced || intersections[index].isVisited)
      {
          return false;
      }
  
      bool result = false;
  
      for(unsigned int i = 0 ; i &lt; intersections[index].neighbours.size() &amp;&amp; !result; ++i)
      {
          if(callerIndex ==  intersections[index].neighbours[i])
              continue;
  
          result = result || shouldBeGuarded(intersections, intersections[index].neighbours[i],index);
      }
      return result;
  }
  int solution(vector&lt;int&gt; &amp;A, vector&lt;int&gt; &amp;B, vector&lt;int&gt; &amp;C)
  {
      // write your code in C++11
  
      vector&lt;Node&gt; intersections;
  
      intersections.resize(A.size()+1, Node());
  
      for(unsigned int i=0 ; i &lt; A.size() ; ++i)
      {
          intersections[A[i]].neighbours.push_back(B[i]);
          intersections[B[i]].neighbours.push_back(A[i]);
  
          if(i &lt; C.size())
              intersections[C[i]].hasPrisoner = true;
      }
  
      for(unsigned int i=0 ; i &lt; intersections.size() ; ++i)
      {
          intersections[i].index = i;
      }
      queue&lt;Node*&gt; guardQueue;
  
      for(unsigned int i=0 ; i &lt; intersections.size() ; ++i)
      {
          if(intersections[i].neighbours.size() == 1)
          {
              if(intersections[i].hasPrisoner)
                  return -1;//Prisoners can't be on exits. If they are there, now way to keep them.
              guardQueue.push(&amp; intersections[i] );
          }
      }
  
      Node* guardNode = NULL;
  
      while(!guardQueue.empty())
      {
          guardNode = guardQueue.front();
          guardQueue.pop();
          if(guardNode-&gt;isVisited)
              continue;
          guardNode-&gt;isVisited = true;
  
          if(guardNode-&gt;neighbours.size() == 1)
          {
              if(intersections[guardNode-&gt;neighbours[0]].hasPrisoner)
                  guardNode-&gt;guardPlaced = true;
              else
              {
                  guardQueue.push(&amp;intersections[guardNode-&gt;neighbours[0]]);
              }
          }
          else
          {
              vector&lt;int&gt; possibleNextMoves;
              for(unsigned int i = 0 ; i &lt; guardNode-&gt;neighbours.size(); ++i)
              {
                  if(intersections[guardNode-&gt;neighbours[i]].hasPrisoner)
                  {
                      guardNode-&gt;guardPlaced = true;
                      break;
                  }
                  if(intersections[guardNode-&gt;neighbours[i]].isVisited || intersections[guardNode-&gt;neighbours[i]].guardPlaced)
                      continue;
                  possibleNextMoves.push_back(guardNode-&gt;neighbours[i]);
              }
  
              if(!guardNode-&gt;guardPlaced &amp;&amp; !possibleNextMoves.empty())
              {
                  if(possibleNextMoves.size() == 1)
                  {
                      guardQueue.push(&amp;intersections[possibleNextMoves[0]]);
                  }
                  else
                  {
                      vector&lt;int&gt; needsGuardList;
  
                      for(unsigned int i = 0 ; i &lt; possibleNextMoves.size(); ++i)
                      {
                          if(shouldBeGuarded(intersections,possibleNextMoves[i],guardNode-&gt;index))
                              needsGuardList.push_back(possibleNextMoves[i]);
                      }
  
                      if(needsGuardList.size() &gt; 1)
                      {
                          guardNode-&gt;guardPlaced = true;
                      }
                      else if(needsGuardList.size() == 1)
                          guardQueue.push(&amp;intersections[needsGuardList[0]]);
                  }
              }
          }
      }
      int counter = 0;
      for(unsigned int i = 0 ; i &lt; intersections.size(); ++i)
      {
          if(intersections[i].guardPlaced)
          {
              counter++;
          }
      }
      return counter;
  }
  </code></pre>