Advertisement
bibaboba12345

лол

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