#include <cstdio> #include <vector> #include <set> using namespace std; void DFS(vector<int> &str, vector<int>::iterator it, vector<int> &res, int dph); int n, m, l, a; int result = -1; vector<int> typ[500]; vector<int> ciag; set<vector<int>> sprawdzone; bool pasuje(vector<int>::iterator str_begin, vector<int>::iterator str_end, vector<int>::iterator wzor_begin, vector<int>::iterator wzor_end) { while(wzor_begin < wzor_end && str_begin < str_end) { if((*wzor_begin++) != (*str_begin++)) return false; } return true; } bool pasuje(vector<int>::reverse_iterator str_begin, vector<int>::reverse_iterator str_end, vector<int>::reverse_iterator wzor_begin, vector<int>::reverse_iterator wzor_end) { while(wzor_begin < wzor_end && str_begin < str_end) { if((*wzor_begin++) != (*str_begin++)) return false; } return true; } void dopasuj_poczatek(vector<int> &str, int dph) { if(sprawdzone.find(str) != sprawdzone.end()) return; sprawdzone.insert(str); vector<int> res; DFS(str,str.begin(), res, dph); for(int i = 0; i < n; ++i) { for(int j = 1; j < (int)typ[i].size(); ++j) { if(pasuje(str.rend() - j, str.rend(), typ[i].rbegin(), typ[i].rend())) { res.push_back(i+1); DFS(str, str.begin() + j, res, dph); res.pop_back(); } } } } void DFS(vector<int> &str, vector<int>::iterator it, vector<int> &res, int dph) { if(it >= str.end()) { if(res.size() == 1 && res[0] == 1) { if(result == -1 || result > dph + 1) { result = dph + 1; } } dopasuj_poczatek(res, dph + 1); } for(int i = 0; i < n; ++i) { if(it < str.end() && pasuje(it, str.end(), typ[i].begin(), typ[i].end())) { res.push_back(i+1); DFS(str, it + typ[i].size(), res, dph); res.pop_back(); } } } int main() { scanf("%d%d",&n,&m); for(int i = 0; i < n; ++i) { scanf("%d", &l); for(int j = 0; j < l; ++j) { scanf("%d", &a); typ[i].push_back(a); } } for(int i = 0; i < m; ++i) { scanf("%d",&a); ciag.push_back(a); } dopasuj_poczatek(ciag, 1); printf("%d\n",result); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | #include <cstdio> #include <vector> #include <set> using namespace std; void DFS(vector<int> &str, vector<int>::iterator it, vector<int> &res, int dph); int n, m, l, a; int result = -1; vector<int> typ[500]; vector<int> ciag; set<vector<int>> sprawdzone; bool pasuje(vector<int>::iterator str_begin, vector<int>::iterator str_end, vector<int>::iterator wzor_begin, vector<int>::iterator wzor_end) { while(wzor_begin < wzor_end && str_begin < str_end) { if((*wzor_begin++) != (*str_begin++)) return false; } return true; } bool pasuje(vector<int>::reverse_iterator str_begin, vector<int>::reverse_iterator str_end, vector<int>::reverse_iterator wzor_begin, vector<int>::reverse_iterator wzor_end) { while(wzor_begin < wzor_end && str_begin < str_end) { if((*wzor_begin++) != (*str_begin++)) return false; } return true; } void dopasuj_poczatek(vector<int> &str, int dph) { if(sprawdzone.find(str) != sprawdzone.end()) return; sprawdzone.insert(str); vector<int> res; DFS(str,str.begin(), res, dph); for(int i = 0; i < n; ++i) { for(int j = 1; j < (int)typ[i].size(); ++j) { if(pasuje(str.rend() - j, str.rend(), typ[i].rbegin(), typ[i].rend())) { res.push_back(i+1); DFS(str, str.begin() + j, res, dph); res.pop_back(); } } } } void DFS(vector<int> &str, vector<int>::iterator it, vector<int> &res, int dph) { if(it >= str.end()) { if(res.size() == 1 && res[0] == 1) { if(result == -1 || result > dph + 1) { result = dph + 1; } } dopasuj_poczatek(res, dph + 1); } for(int i = 0; i < n; ++i) { if(it < str.end() && pasuje(it, str.end(), typ[i].begin(), typ[i].end())) { res.push_back(i+1); DFS(str, it + typ[i].size(), res, dph); res.pop_back(); } } } int main() { scanf("%d%d",&n,&m); for(int i = 0; i < n; ++i) { scanf("%d", &l); for(int j = 0; j < l; ++j) { scanf("%d", &a); typ[i].push_back(a); } } for(int i = 0; i < m; ++i) { scanf("%d",&a); ciag.push_back(a); } dopasuj_poczatek(ciag, 1); printf("%d\n",result); } |