vadimk772336

божеский код + пожарник Ванес

Mar 14th, 2022
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.89 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <map>
  5. using namespace std;
  6.  
  7. struct vertex
  8. {
  9. bool isterminal = false;
  10. // mapchar,int adj_list; // Заменить на массив длины 26
  11. int adj_list[26];
  12. bool is_exist[26];
  13. // vector<int> adj_list(26,-1);
  14. int list_size = 0;
  15. int number_vertex;
  16. };
  17.  
  18. struct my_pair
  19. {
  20. int a;
  21. int b;
  22. };
  23.  
  24. struct vertex_2
  25. {
  26. int u;
  27. int v;
  28. bool isterminal = false;
  29. bool isvisited = false;
  30. struct my_pair adj_list[26];
  31. bool is_exist[26] = { false };
  32. int number_in_array;
  33. };
  34.  
  35.  
  36.  
  37.  
  38. struct adj_vertex
  39. {
  40. int number_vertex;
  41. char symbol;
  42. };
  43.  
  44. void addEdge(int i, int j, char symbol, struct vertex* DFA)
  45. {
  46. int symbol_idx = int(symbol) - 97;
  47. DFA[i].adj_list[symbol_idx] = j;
  48. DFA[i].is_exist[symbol_idx] = true;
  49. DFA[i].list_size++;
  50. }
  51.  
  52. void Fill_DFA(int n, int k, int l, vector<char>& alphabet, struct vertex* DFA)
  53. {
  54. int u, v, c_idx;
  55. char c;
  56. int terminals[k];
  57.  
  58. int indicators[26] = { 0 };
  59.  
  60. for (int i = 0; i < k; ++i)
  61. cin >> terminals[i];
  62.  
  63. for (int i = 0; i < k; ++i)
  64. {
  65. DFA[terminals[i]].isterminal = true;
  66. }
  67.  
  68.  
  69. for (int i = 0; i < n * l; ++i)
  70. {
  71. cin >> u >> c >> v;
  72. // DFA.addEdge(u,v,c, DFA);
  73. addEdge(u, v, c, DFA);
  74.  
  75. //Запоминаю алфавит автоматов
  76. c_idx = int(c) - 97;
  77. if (indicators[c_idx] == 0)
  78. {
  79. alphabet.push_back(c);
  80. indicators[c_idx] = 1;
  81. }
  82. else
  83. indicators[c_idx] = 1;
  84. }
  85.  
  86. return;
  87. }
  88.  
  89.  
  90. void display(struct vertex* DFA, int n)
  91. {
  92. cout << "\n print:" << endl;
  93. for (int i = 0; i < n; i++)
  94. {
  95. cout << "vertex: " << i << " ";
  96. if (DFA[i].isterminal)
  97. cout << "isterminal"
  98. << " ";
  99.  
  100. cout << "adj_vertexes: ";
  101. for (int j = 0; j < 26; ++j)
  102. {
  103. if (DFA[i].is_exist[j] == true)
  104. std::cout << "(" << char(j + 97) << "," << DFA[i].adj_list[j] << "); ";
  105. }
  106. cout << endl;
  107. }
  108. }
  109.  
  110. void clean_DFA(struct vertex* DFA, int n)
  111. {
  112. for (int i = 0; i < n; i++)
  113. {
  114. DFA[i].isterminal = false;
  115. DFA[i].list_size = 0;
  116.  
  117. for (int j = 0; j < 26; ++j)
  118. {
  119. DFA[i].adj_list[j] = -1; //Эта строчка ломает код
  120. DFA[i].is_exist[j] = false;
  121. }
  122. }
  123. }
  124.  
  125. void display2(struct vertex_2* DFA, int n)
  126. {
  127. cout << "\n print:" << endl;
  128. for (int i = 0; i < n; i++)
  129. {
  130. cout << "vertex: " << i << " ";
  131. if (DFA[i].isterminal)
  132. cout << "isterminal" << " ";
  133.  
  134. cout << "adj_vertexes: ";
  135. for (int j = 0; j < 26; ++j)
  136. {
  137. if (DFA[i].is_exist[j] == true)
  138. std::cout << "(" << char(j + 97) << ", (" << DFA[i].adj_list[j].a << ", )" << DFA[i].adj_list[j].b; "); ";
  139. }
  140. cout << endl;
  141. }
  142. }
  143.  
  144. int main()
  145. {
  146. // n — колво состояний. k — колво терминальных состояний. l — колво букв в алфавите.
  147. int n1, k1, l1;
  148. vector<char> alphabet1;
  149. int n2, k2, l2;
  150. vector<char> alphabet2;
  151. cin >> n1 >> k1 >> l1;
  152. vertex DFA1[n1];
  153. clean_DFA(DFA1, n1);
  154. Fill_DFA(n1, k1, l1, alphabet1, DFA1);
  155.  
  156.  
  157. cin >> n2 >> k2 >> l2;
  158. vertex DFA2[n2];
  159. clean_DFA(DFA2, n2);
  160. Fill_DFA(n2, k2, l2, alphabet2, DFA2);
  161.  
  162.  
  163.  
  164. int v1,v2;
  165. int number_in_array;
  166. cout << " start1" << endl;
  167. int N = n1*n2;
  168. struct vertex_2 dec_graph[N];
  169. vertex_2 buff;
  170. struct my_pair dec_ver;
  171. cout << " start2" << endl;
  172.  
  173. for (int i =0; i < n1; ++i)
  174. {
  175. for (int j =0; j < n2; ++j)
  176. {
  177. buff.u = i;
  178. buff.v = j;
  179. buff.isterminal = (DFA1[i].isterminal != DFA2[j].isterminal);
  180. buff.number_in_array = i*n2+j;
  181.  
  182. for (int k = 0; k < 26; ++k)
  183. {
  184. if (DFA1[i].is_exist[k] && DFA2[j].is_exist[k])
  185. {
  186. dec_ver.a = DFA1[i].adj_list[k]; //Куда переходит авт1 по символу c
  187. dec_ver.b = DFA2[j].adj_list[k]; //Куда переходит авт2 по символу c
  188. buff.adj_list[k] = dec_ver; //по этой штуке понятно к кому обращаться при обходе
  189. buff.is_exist[k] = true;
  190. }
  191. else
  192. {
  193. dec_graph[i*n2+j].is_exist[k] = false;
  194. }
  195. }
  196.  
  197. dec_graph[i*n2+j] = buff;
  198. }
  199. }
  200. display(DFA1, n1);
  201. display(DFA2, n2);
  202.  
  203. display2(dec_graph, N);
  204.  
  205. return 0;
  206. }
  207.  
Advertisement
Add Comment
Please, Sign In to add comment