Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Authors
- Emilio Chavez Madero A00816752
- Adrian Silva Mendez A01281337
- Date : 20/04/2017
- Description: PROYECTO DOS, RAILROAD
- */
- #include <iostream>
- #include <cmath>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <stack>
- #include <queue>
- #include <map>
- #include <set>
- #include <cstring>
- using namespace std;
- //---- definitions ----//
- typedef vector<int> vi;
- bool isPossible = false;
- long long int tam1, tam2;
- long long int v1[1001], v2[1001], v3[2000];
- bool mat[1001][1001];
- bool backtrackingSol(long long int pos1, long long int pos2, long long int len)
- {
- if(pos1+pos2==len)
- {
- return true;
- }
- 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));
- return mat[pos1][pos2];
- }
- // ---- main ---- //
- int main()
- {
- long long int len1,len2,len3;
- fill(v1,v1+1001,-1);
- fill(v2,v2+1001,-1);
- while(1){
- memset(mat,true,1001*1001);
- // getting data
- cin >> len1 >> len2;
- tam1 = len1;
- tam2 = len2;
- if(!len1 && !len2)
- break;
- len3 = len1 + len2;
- // filling stacksi
- long long int temp;
- for(long long int i = 0; i<len1; i++){
- cin >> v1[i];
- }
- for(long long int i = 0; i<len2; i++){
- cin >> v2[i];
- }
- for(long long int i = 0; i<len3; i++)
- {
- cin >> v3[i];
- }
- // testing the sequence
- isPossible = backtrackingSol(0,0,len3);
- //cout << "out" << endl;
- if(isPossible)
- cout << "possible\n";
- else
- cout << "not possible\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement