Derga

Untitled

Jun 13th, 2024
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.49 KB | None | 0 0
  1. //https://codeforces.com/contest/1985/problem/H1
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <vector>
  5. #include <string>
  6. #include <cstdint>
  7. #include <iostream>
  8. #include <set>
  9. #include <numeric>
  10. #include <queue>
  11. #include <map>
  12. #include <iomanip>
  13. #include <sstream>
  14. #include <unordered_map>
  15.  
  16. using namespace std;
  17.  
  18. void Dfs(const vector<vector<char>>& field, vector<vector<bool>>& is_visited,
  19. vector<vector<int>>& types, int type, int i, int j, int& size)
  20. {
  21. is_visited[i][j] = true;
  22. ++size;
  23. types[i][j] = type;
  24. for (int di = -1; di <= 1; ++di) {
  25. for (int dj = -1; dj <= 1; ++dj) {
  26. if (di * di + dj * dj != 1) continue;
  27.  
  28. int ni = i + di;
  29. int nj = j + dj;
  30. if (ni < 0 || field.size() <= ni || nj < 0 || field.front().size() <= nj) continue;
  31. if (is_visited[ni][nj]) continue;
  32. if (field[ni][nj] == '.') continue;
  33.  
  34. Dfs(field, is_visited, types, type, ni, nj, size);
  35. }
  36. }
  37. }
  38.  
  39. int main() {
  40. ios::sync_with_stdio(0);
  41. cin.tie(0);
  42.  
  43. int t;
  44. cin >> t;
  45. while (t--) {
  46. int rows_count, columns_count;
  47. cin >> rows_count >> columns_count;
  48. vector<vector<char>> field(rows_count, vector<char>(columns_count));
  49. for (auto& row : field) for (auto& elem : row) cin >> elem;
  50.  
  51. vector<vector<bool>> is_visited(rows_count, vector<bool>(columns_count, false));
  52. vector<vector<int>> types(rows_count, vector<int>(columns_count, 0));
  53. vector<int> type_size = {0};
  54. int type = 1;
  55. for (int i = 0; i < field.size(); ++i) {
  56. for (int j = 0; j < field.front().size(); ++j) {
  57. if (field[i][j] == '.') continue;
  58. if (is_visited[i][j]) continue;
  59.  
  60. int size = 0;
  61. Dfs(field, is_visited, types, type, i, j, size);
  62. type_size.push_back(size);
  63. ++type;
  64. }
  65. }
  66.  
  67. int result = 0;
  68. vector<int> t(type_size.size(), -1);
  69. for (int i = 0; i < field.size(); ++i) {
  70. int cur_result = 0;
  71. for (int j = 0; j < field.front().size(); ++j) {
  72. if (field[i][j] != '.' && t[types[i][j]] != i) {
  73. cur_result += type_size[types[i][j]];
  74. t[types[i][j]] = i;
  75. }
  76. if (field[i][j] == '.') ++cur_result;
  77.  
  78. for (int di = -1; di <= 1; ++di) {
  79. for (int dj = -1; dj <= 1; ++dj) {
  80. if (di * di + dj * dj != 1) continue;
  81.  
  82. int ni = i + di;
  83. int nj = j + dj;
  84. if (ni < 0 || field.size() <= ni || nj < 0 || field.front().size() <= nj) continue;
  85. if (types[ni][nj] == 0) continue;
  86.  
  87. if (t[types[ni][nj]] != i) {
  88. cur_result += type_size[types[ni][nj]];
  89. t[types[ni][nj]] = i;
  90. }
  91. }
  92. }
  93. }
  94. result = max(result, cur_result);
  95. }
  96.  
  97. for (int& elem : t) elem = -1;
  98.  
  99. for (int j = 0; j < field.front().size(); ++j) {
  100. int cur_result = 0;
  101. for (int i = 0; i < field.size(); ++i) {
  102. if (field[i][j] != '.' && t[types[i][j]] != j) {
  103. cur_result += type_size[types[i][j]];
  104. t[types[i][j]] = j;
  105. }
  106. if (field[i][j] == '.') ++cur_result;
  107.  
  108. for (int di = -1; di <= 1; ++di) {
  109. for (int dj = -1; dj <= 1; ++dj) {
  110. if (di * di + dj * dj != 1) continue;
  111.  
  112. int ni = i + di;
  113. int nj = j + dj;
  114. if (ni < 0 || field.size() <= ni || nj < 0 || field.front().size() <= nj) continue;
  115. if (types[ni][nj] == 0) continue;
  116.  
  117. if (t[types[ni][nj]] != j) {
  118. cur_result += type_size[types[ni][nj]];
  119. t[types[ni][nj]] = j;
  120. }
  121. }
  122. }
  123. }
  124. result = max(result, cur_result);
  125. }
  126.  
  127. cout << result << '\n';
  128. }
  129.  
  130. return 0;
  131. }
  132. /*
  133. tes1
  134. 1
  135. 3 5
  136. .#.#.
  137. ..#..
  138. .#.#.
  139.  
  140. 9
  141. test2
  142. 1
  143. 5 5
  144. #...#
  145. ....#
  146. #...#
  147. .....
  148. ...##
  149.  
  150. 11
  151. test3
  152. 1
  153. 4 2
  154. ..
  155. #.
  156. #.
  157. .#
  158.  
  159. 6
  160. */
Advertisement
Add Comment
Please, Sign In to add comment