Advertisement
bibaboba12345

душное говно

Nov 5th, 2021
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.22 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma GCC target ("avx2")
  3. #pragma GCC optimization ("O3")
  4. #pragma GCC optimization ("unroll-loops")
  5. #pragma comment (linker, "/STACK:64000000")
  6. #include <iostream>
  7. #include <algorithm>
  8. #include <vector>
  9. #include <cmath>
  10. #include <random>
  11. #include <unordered_set>
  12. #include <set>
  13. using namespace std;
  14. const int N = 3e5;
  15. long long t, x,y, n, r, b, m, lx, rx, ly, ry;
  16. string s;
  17. int vis[2002][2002];
  18. char matr[2002][2002];
  19. int d[2002][2002];
  20. void ClearVis() {
  21. for (int i = 0; i < n; i++) {
  22. for (int j = 0; j < m; j++) {
  23. vis[i][j] = 0;
  24. }
  25. }
  26. }
  27. void ClearD() {
  28. for (int i = 0; i < n; i++) {
  29. for (int j = 0; j < m; j++) {
  30. d[i][j] = -1;
  31. }
  32. }
  33. }
  34.  
  35. vector<pair <int, int> > cycle, stack;
  36. vector<int> stolb, strok;
  37.  
  38. void FindCyc(int str, int col) {
  39. pair<int, int> nxt = {str,col};
  40. while (true) {
  41. stack.push_back(nxt);
  42. vis[nxt.first][nxt.second] = 2;
  43. if (matr[nxt.first][nxt.second] == 'U') {
  44. nxt.first--;
  45. }
  46. else if (matr[nxt.first][nxt.second] == 'D') {
  47. nxt.first++;
  48. }
  49. else if (matr[nxt.first][nxt.second] == 'L') {
  50. nxt.second--;
  51. }
  52. else if (matr[nxt.first][nxt.second] == 'R') {
  53. nxt.second++;
  54. }
  55. if (nxt.first < 0 || nxt.first >= n || nxt.second < 0 || nxt.second >= m) {
  56. int cnt = 1;
  57. while (!stack.empty()) {
  58. d[stack[stack.size() - 1].first][stack[stack.size() - 1].second] = cnt;
  59. vis[stack[stack.size() - 1].first][stack[stack.size() - 1].second] = 1;
  60. stack.pop_back();
  61. cnt++;
  62. }
  63. return;
  64. }
  65. if (vis[nxt.first][nxt.second] == 1) {
  66. int cnt = d[nxt.first][nxt.second] + 1;
  67. while (!stack.empty()) {
  68. d[stack[stack.size() - 1].first][stack[stack.size() - 1].second] = cnt;
  69. vis[stack[stack.size() - 1].first][stack[stack.size() - 1].second] = 1;
  70. stack.pop_back();
  71. cnt++;
  72. }
  73. return;
  74. }
  75. if (vis[nxt.first][nxt.second] == 2) {
  76. cycle.clear();
  77. while (stack[stack.size() - 1] != nxt) {
  78. cycle.push_back(stack[stack.size() - 1]);
  79. stack.pop_back();
  80. }
  81. cycle.push_back(stack[stack.size() - 1]);
  82. stack.pop_back();
  83.  
  84. for (int i = 0; i < cycle.size(); i++) {
  85. d[cycle[i].first][cycle[i].second] = cycle.size();
  86. vis[cycle[i].first][cycle[i].second] = 1;
  87. }
  88. if (stack.empty()) {
  89. return;
  90. }
  91. nxt = stack[stack.size() - 1];
  92. stack.pop_back();
  93. }
  94. }
  95. return;
  96. }
  97.  
  98. int main()
  99. {
  100. ios::sync_with_stdio(false);
  101. cin.tie(0);
  102. //freopen("input.txt", "r", stdin);
  103. cin >> t;
  104. for (int I = 0; I < t; I++) {
  105. cin >> n >> m;
  106. for (int i = 0; i < n; i++) {
  107. for (int j = 0; j < m; j++) {
  108. cin >> matr[i][j];
  109. }
  110. }
  111. cycle.reserve(n * m + 1);
  112. ClearD();
  113. /*stolb.resize(n);
  114. strok.resize(m);
  115. for (int i = 0; i < n; i++) {
  116. stolb[i] = i;
  117. }
  118. for (int i = 0; i < n * 3; i++) {
  119. int u = rand() % n;
  120. int v = rand() % n;
  121. swap(stolb[u], stolb[v]);
  122. }
  123. for (int i = 0; i < m; i++) {
  124. strok[i] = i;
  125. }
  126. for (int i = 0; i < m * 3; i++) {
  127. int u = rand() % m;
  128. int v = rand() % m;
  129. swap(strok[u], strok[v]);
  130. }*/
  131.  
  132. for (int i = 0; i < n; i++) {
  133. for (int j = 0; j < m; j++) {
  134. if (!vis[i][j]) {
  135. stack.clear();
  136. FindCyc(i, j);
  137. }
  138. }
  139. }
  140.  
  141. int mxans = 0, a_i = 0, a_j = 0;
  142. for (int i = 0; i < n; i++) {
  143. for (int j = 0; j < m; j++) {
  144. if (d[i][j] > mxans) {
  145. mxans = d[i][j];
  146. a_i = i;
  147. a_j = j;
  148. }
  149. }
  150. }
  151. cout << a_i + 1 << " " << a_j + 1 << " " << mxans << "\n";
  152. ClearVis(); ClearD();
  153. }
  154. }
  155.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement