Advertisement
Guest User

Untitled

a guest
Nov 20th, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.03 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <queue>
  6. #include <stack>
  7. #include <cmath>
  8. #include <iomanip>
  9. #include <fstream>
  10. #include <map>
  11. #include <set>
  12.  
  13. using namespace std;
  14. struct ver
  15. {
  16. vector<int> np;
  17. ver() {
  18. np.resize(4, -1);
  19. }
  20. };
  21. bool fl = false;
  22. vector<ver> g1, g2;
  23. vector<pair<int, int>> go = { { -1, 0 } ,{ 0, 1 },{ 1, 0 } ,{ 0, -1 } };
  24. vector<vector<char>> mat(100, vector <char>(100, '.'));
  25. void dfs1(int x, int y, int v, char cv, int pr)
  26. {
  27. mat[x][y] = cv;
  28. for (int i = 0; i != 4; i++)
  29. {
  30. if (g1[v].np[i] == -1)
  31. {
  32. continue;
  33. }
  34. pair<int, int> e = go[(i + pr) % 4];
  35. int xx = x + e.first;
  36. int yy = y + e.second;
  37. if (mat[xx][yy] == '.')
  38. {
  39. dfs1(xx, yy, g1[v].np[i], cv, pr);
  40. }
  41. else
  42. {
  43. if (mat[xx][yy] == '2')
  44. {
  45. fl = true;
  46. return;
  47. }
  48. }
  49. }
  50. return;
  51. }
  52. void dfs2(int x, int y, int v, char cv, int pr)
  53. {
  54. mat[x][y] = cv;
  55. for (int i = 0; i != 4; i++)
  56. {
  57. if (g2[v].np[i] == -1)
  58. {
  59. continue;
  60. }
  61. pair<int, int> e = go[(i + pr) % 4];
  62. int xx = x + e.first;
  63. int yy = y + e.second;
  64. if (mat[xx][yy] == '.')
  65. {
  66. dfs2(xx, yy, g2[v].np[i], cv, pr);
  67. }
  68. }
  69. return;
  70. }
  71. int kol = 0;
  72. bool gr = false;
  73. vector<vector<bool>> used(100, vector<bool>(100, false));
  74. void dfs(int x, int y)
  75. {
  76. kol++;
  77. used[x][y] = true;
  78. for (int i = 0; i != 4; i++)
  79. {
  80. pair<int, int> e = go[i];
  81. int xx = x + e.first;
  82. int yy = y + e.second;
  83. if (xx > -1 && xx < 100 && yy > -1 && yy < 100)
  84. {
  85. if (mat[xx][yy] == '.' && used[xx][yy] == false)
  86. {
  87. dfs(xx, yy);
  88. }
  89. }
  90. else
  91. {
  92. gr = true;
  93. }
  94. }
  95. }
  96. int main()
  97. {
  98. ios_base::sync_with_stdio(false);
  99. cin.tie(0);
  100. cout.tie(0);
  101. ifstream cin("input.txt");
  102. //ifstream cin("program.in");
  103. //ofstream cout("program.out");
  104. int cur = 0;
  105. int h1, h2;
  106. cin >> h1 >> h2;
  107. vector<vector<char>> col1(h1, vector<char>(h2));
  108. vector<vector<int>> num1(h1, vector<int>(h2, -1));
  109. for (int i = 0; i != h1; i++)
  110. {
  111. for (int j = 0; j != h2; j++)
  112. {
  113. cin >> col1[i][j];
  114. if (col1[i][j] == '*')
  115. {
  116. num1[i][j] = cur;
  117. cur++;
  118. }
  119. }
  120. }
  121. g1.resize(cur);
  122. for (int i = 0; i != h1; i++)
  123. {
  124. for (int j = 0; j != h2; j++)
  125. {
  126. if (col1[i][j] == '*')
  127. {
  128. for (int k = 0; k != 4; k++)
  129. {
  130. pair<int, int> e = go[k];
  131. int x = i + e.first;
  132. int y = j + e.second;
  133. if (x > -1 && x < h1 && y > -1 && y < h2)
  134. {
  135. if (col1[x][y] == '*')
  136. {
  137. g1[num1[i][j]].np[k] = num1[x][y];
  138. }
  139. }
  140. }
  141. }
  142. }
  143. }
  144. cur = 0;
  145. cin >> h1 >> h2;
  146. vector<vector<char>> col2(h1, vector<char>(h2));
  147. vector<vector<int>> num2(h1, vector<int>(h2, -1));
  148. for (int i = 0; i != h1; i++)
  149. {
  150. for (int j = 0; j != h2; j++)
  151. {
  152. cin >> col2[i][j];
  153. if (col2[i][j] == '*')
  154. {
  155. num2[i][j] = cur;
  156. cur++;
  157. }
  158. }
  159. }
  160. g2.resize(cur);
  161. for (int i = 0; i != h1; i++)
  162. {
  163. for (int j = 0; j != h2; j++)
  164. {
  165. if (col2[i][j] == '*')
  166. {
  167. for (int k = 0; k != 4; k++)
  168. {
  169. pair<int, int> e = go[k];
  170. int x = i + e.first;
  171. int y = j + e.second;
  172. if (x > -1 && x < h1 && y > -1 && y < h2)
  173. {
  174. if (col2[x][y] == '*')
  175. {
  176. g2[num2[i][j]].np[k] = num2[x][y];
  177. }
  178. }
  179. }
  180. }
  181. }
  182. }
  183. dfs2(50, 50, 0, '2', 0);
  184. int mx = -1;
  185. for (int x1 = 40; x1 != 60; x1++)
  186. {
  187. for (int y1 = 40; y1 != 60; y1++)
  188. {
  189. for (int p = 0; p != 4; p++)
  190. {
  191. fl = false;
  192. if (mat[x1][y1] == '.')
  193. {
  194. dfs1(x1, y1, 0, '1', p);
  195. }
  196. if (fl)
  197. {
  198. continue;
  199. }
  200. for (int i = 0; i != 100; i++)
  201. {
  202. for (int j = 0; j != 100; j++)
  203. {
  204. if (used[i][j] == false)
  205. {
  206. gr = false;
  207. kol = 0;
  208. dfs(i, j);
  209. if (gr)
  210. {
  211. continue;
  212. }
  213. mx = max(mx, kol);
  214. }
  215. }
  216. }
  217. used.resize(100, vector<bool>(100, false));
  218. mat.resize(100, vector<char>(100, '.'));
  219. dfs2(50, 50, 0, '2', 0);
  220. }
  221. }
  222. }
  223. cout << mx;
  224. return 0;
  225. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement