tobast

Untitled

Oct 12th, 2012
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int MAX_CASES = 1000, INFINITE=1000*1000*1000;
  6.  
  7. int values[MAX_CASES];
  8. int movesTo[MAX_CASES];
  9. int nbCases = 0;
  10.  
  11. void pathfinder(int pos, int curMv)
  12. {
  13.     if(pos < 0 || pos >= nbCases || curMv >= movesTo[pos] || values[pos] == -1)
  14.         return;
  15.     movesTo[pos] = curMv;
  16.  
  17.     pathfinder(pos-1,curMv+1);
  18.     pathfinder(pos+1,curMv+1);
  19.     pathfinder(values[pos],curMv+1);
  20. }
  21.  
  22. int main(void)
  23. {
  24.     cin >> nbCases;
  25.     for(int pos=0; pos<nbCases; pos++)
  26.     {
  27.         movesTo[pos] = INFINITE;
  28.         cin >> values[pos];
  29.     }
  30.    
  31.     if(values[nbCases-1] == -1)
  32.         cout << "-1\n";
  33.     else
  34.     {
  35.         pathfinder(0,0);
  36.         if(movesTo[nbCases-1] == INFINITE)
  37.             cout << "-1\n";
  38.         else
  39.             cout << movesTo[nbCases-1] << "\n";
  40.     }
  41. /*
  42.    for(int pos=0; pos<nbCases; pos++)
  43.         cout << movesTo[pos] << "\t";
  44.     cout << "\n";
  45. */
  46.     return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment