Advertisement
didedoshka

Untitled

Feb 8th, 2023
967
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.54 KB | None | 0 0
  1. #define _USE_MATH_DEFINES
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <queue>
  7. #include <cmath>
  8. #include <set>
  9. #include <stack>
  10. #include <bitset>
  11. #include <map>
  12. #include <ctime>
  13. #include <numeric>
  14. #include <random>
  15. #include <cassert>
  16.  
  17. //#define int long long
  18. #define uint unsigned long long
  19. #define double long double
  20.  
  21. #ifdef DIDEDOSHKA
  22. #define start cout.setf(ios::fixed); cout.precision(10); freopen("../input.txt", "r", stdin); int START = clock()
  23. #define finish cout << "\ntime: " << (clock() - START) / (double)(CLOCKS_PER_SEC); return 0
  24. #else
  25. #define start cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(10)
  26. #define finish return 0
  27. #endif
  28.  
  29. using namespace std;
  30.  
  31.  
  32. //vector input
  33. template<typename T>
  34. istream &operator>>(istream &is, vector<T> &vec) {
  35.     for (auto &i: vec) {
  36.         is >> i;
  37.     }
  38.     return is;
  39. }
  40.  
  41. //vector output
  42. template<typename T>
  43. ostream &operator<<(ostream &os, vector<T> &vec) {
  44.     for (T i: vec) {
  45.         os << i << ' ';
  46.     }
  47.     return os;
  48. }
  49.  
  50. //2 dimensional vector output
  51. template<typename T>
  52. ostream &operator<<(ostream &os, vector<vector<T>> &vec) {
  53.     for (vector<T> i: vec) {
  54.         os << i << '\n';
  55.     }
  56.     return os;
  57. }
  58.  
  59. const int N = 4'000'001;
  60.  
  61. int a[N];
  62. int len[N];
  63. int leni[N];
  64. int8_t used[N];
  65. vector<bool> h;
  66.  
  67. //vector<int> a;
  68. //vector<int> len;
  69. //vector<int> leni;
  70. //vector<int> used;
  71. //vector<int> h;
  72. bool flag;
  73.  
  74. void dfs(int v) {
  75.     used[v] = 1;
  76.     if (a[v] != -1) {
  77.         if (used[a[v]] == 1) {
  78.             h[a[v]] = 1;
  79.             len[v] = leni[v] - leni[a[v]] + 1;
  80.             flag = true;
  81.         } else if (used[a[v]] == 2) {
  82.             len[v] = len[a[v]] + 1;
  83.         } else {
  84.             leni[a[v]] = leni[v] + 1;
  85.             dfs(a[v]);
  86.             if (flag) {
  87.                 len[v] = len[a[v]];
  88.             } else {
  89.                 len[v] = len[a[v]] + 1;
  90.             }
  91.             if (h[v]) {
  92.                 flag = false;
  93.             }
  94.         }
  95.     } else {
  96.         len[v] = 1;
  97.     }
  98.     used[v] = 2;
  99. }
  100.  
  101. void solve() {
  102.     int vs, hs;
  103.     cin >> vs >> hs;
  104.     int n = vs * hs;
  105.  
  106. //    a.assign(n, -1);
  107. //    used.assign(n, 0);
  108. //    len.assign(n, 0);
  109. //    leni.assign(n, 0);
  110.     h.assign(n, 0);
  111.  
  112.     for (int i = 0; i < n; ++i) {
  113.         a[i] = -1;
  114.         used[i] = 0;
  115.         len[i] = 0;
  116.         leni[i] = 0;
  117. //        h[i] = 0;
  118.     }
  119.     for (int i = 0; i < vs; ++i) {
  120.         string inp;
  121.         cin >> inp;
  122.         for (int j = 0; j < hs; ++j) {
  123.             if (inp[j] == 'U') {
  124.                 if (i - 1 >= 0) {
  125.                     a[i * hs + j] = (i - 1) * hs + j;
  126.                 }
  127.             } else if (inp[j] == 'D') {
  128.                 if (i + 1 < vs) {
  129.                     a[i * hs + j] = (i + 1) * hs + j;
  130.                 }
  131.             } else if (inp[j] == 'L') {
  132.                 if (j - 1 >= 0) {
  133.                     a[i * hs + j] = i * hs + (j - 1);
  134.                 }
  135.             } else {
  136.                 if (j + 1 < hs) {
  137.                     a[i * hs + j] = i * hs + (j + 1);
  138.                 }
  139.             }
  140.         }
  141.     }
  142.  
  143.     for (int i = 0; i < n; ++i) {
  144.         if (!used[i]) {
  145.             dfs(i);
  146.         }
  147.     }
  148.  
  149.     auto ans = max_element(len, len + n);
  150.     int i = distance(len, ans);
  151.     cout << (i / hs) + 1 << ' ' << (i % hs) + 1 << ' ';
  152.     cout << *ans << '\n';
  153.    
  154. }
  155.  
  156. int32_t main() {
  157.     start;
  158.  
  159.     int t;
  160.     cin >> t;
  161.     while (t--) {
  162.         solve();
  163.     }
  164.  
  165.     finish;
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement