Advertisement
Guest User

Untitled

a guest
Apr 24th, 2017
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. /*
  2.     Authors
  3.  Emilio Chavez Madero   A00816752
  4.  Adrian Silva Mendez        A01281337
  5.  
  6.     Date    : 20/04/2017
  7.  
  8.     Description: PROYECTO DOS, RAILROAD
  9.  */
  10. #include <iostream>
  11. #include <cmath>
  12. #include <string>
  13. #include <vector>
  14. #include <algorithm>
  15. #include <stack>
  16. #include <queue>
  17. #include <map>
  18. #include <set>
  19. #include <cstring>
  20.  
  21.  
  22. using namespace std;
  23. //----  definitions ----//
  24. typedef vector<int> vi;
  25.  
  26. bool isPossible = false;
  27. long long int tam1, tam2;
  28. long long int v1[1001], v2[1001], v3[2000];
  29. bool mat[1001][1001];
  30.  
  31. bool backtrackingSol(long long int pos1, long long int pos2, long long int len)
  32. {
  33.     if(pos1+pos2==len)
  34.     {
  35.         return true;
  36.     }
  37.     mat[pos1][pos2] = ((v1[pos1]==v3[pos1+pos2]&&mat[pos1+1][pos2]?backtrackingSol(pos1+1,pos2,len):false)||(v2[pos2]==v3[pos1+pos2]&&mat[pos1][pos2+1]?backtrackingSol(pos1,pos2+1,len):false));
  38.     return mat[pos1][pos2];
  39. }
  40.  
  41. //  ---- main ---- //
  42. int main()
  43. {
  44.     long long int len1,len2,len3;
  45.     fill(v1,v1+1001,-1);
  46.     fill(v2,v2+1001,-1);
  47.     while(1){
  48.         memset(mat,true,1001*1001);
  49.         // getting data
  50.         cin >> len1 >> len2;
  51.         tam1 = len1;
  52.         tam2 = len2;
  53.  
  54.         if(!len1 && !len2)
  55.             break;
  56.         len3 = len1 + len2;
  57.  
  58.         // filling stacksi
  59.         long long int temp;
  60.         for(long long int i = 0; i<len1; i++){
  61.             cin >> v1[i];
  62.         }
  63.         for(long long int i = 0; i<len2; i++){
  64.             cin >> v2[i];
  65.         }
  66.         for(long long int i = 0; i<len3; i++)
  67.         {
  68.             cin >> v3[i];
  69.         }
  70.         // testing the sequence
  71.         isPossible = backtrackingSol(0,0,len3);
  72.         //cout << "out" << endl;
  73.  
  74.         if(isPossible)
  75.             cout << "possible\n";
  76.         else
  77.             cout << "not possible\n";
  78.     }
  79.  
  80.  
  81.     return 0;
  82.  
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement