Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _USE_MATH_DEFINES
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <queue>
- #include <cmath>
- #include <set>
- #include <stack>
- #include <bitset>
- #include <map>
- #include <ctime>
- #include <numeric>
- #include <random>
- #include <cassert>
- //#define int long long
- #define uint unsigned long long
- #define double long double
- #ifdef DIDEDOSHKA
- #define start cout.setf(ios::fixed); cout.precision(10); freopen("../input.txt", "r", stdin); int START = clock()
- #define finish cout << "\ntime: " << (clock() - START) / (double)(CLOCKS_PER_SEC); return 0
- #else
- #define start cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(10)
- #define finish return 0
- #endif
- using namespace std;
- //vector input
- template<typename T>
- istream &operator>>(istream &is, vector<T> &vec) {
- for (auto &i: vec) {
- is >> i;
- }
- return is;
- }
- //vector output
- template<typename T>
- ostream &operator<<(ostream &os, vector<T> &vec) {
- for (T i: vec) {
- os << i << ' ';
- }
- return os;
- }
- //2 dimensional vector output
- template<typename T>
- ostream &operator<<(ostream &os, vector<vector<T>> &vec) {
- for (vector<T> i: vec) {
- os << i << '\n';
- }
- return os;
- }
- const int N = 4'000'001;
- int a[N];
- int len[N];
- int leni[N];
- int8_t used[N];
- vector<bool> h;
- //vector<int> a;
- //vector<int> len;
- //vector<int> leni;
- //vector<int> used;
- //vector<int> h;
- bool flag;
- void dfs(int v) {
- used[v] = 1;
- if (a[v] != -1) {
- if (used[a[v]] == 1) {
- h[a[v]] = 1;
- len[v] = leni[v] - leni[a[v]] + 1;
- flag = true;
- } else if (used[a[v]] == 2) {
- len[v] = len[a[v]] + 1;
- } else {
- leni[a[v]] = leni[v] + 1;
- dfs(a[v]);
- if (flag) {
- len[v] = len[a[v]];
- } else {
- len[v] = len[a[v]] + 1;
- }
- if (h[v]) {
- flag = false;
- }
- }
- } else {
- len[v] = 1;
- }
- used[v] = 2;
- }
- void solve() {
- int vs, hs;
- cin >> vs >> hs;
- int n = vs * hs;
- // a.assign(n, -1);
- // used.assign(n, 0);
- // len.assign(n, 0);
- // leni.assign(n, 0);
- h.assign(n, 0);
- for (int i = 0; i < n; ++i) {
- a[i] = -1;
- used[i] = 0;
- len[i] = 0;
- leni[i] = 0;
- // h[i] = 0;
- }
- for (int i = 0; i < vs; ++i) {
- string inp;
- cin >> inp;
- for (int j = 0; j < hs; ++j) {
- if (inp[j] == 'U') {
- if (i - 1 >= 0) {
- a[i * hs + j] = (i - 1) * hs + j;
- }
- } else if (inp[j] == 'D') {
- if (i + 1 < vs) {
- a[i * hs + j] = (i + 1) * hs + j;
- }
- } else if (inp[j] == 'L') {
- if (j - 1 >= 0) {
- a[i * hs + j] = i * hs + (j - 1);
- }
- } else {
- if (j + 1 < hs) {
- a[i * hs + j] = i * hs + (j + 1);
- }
- }
- }
- }
- for (int i = 0; i < n; ++i) {
- if (!used[i]) {
- dfs(i);
- }
- }
- auto ans = max_element(len, len + n);
- int i = distance(len, ans);
- cout << (i / hs) + 1 << ' ' << (i % hs) + 1 << ' ';
- cout << *ans << '\n';
- }
- int32_t main() {
- start;
- int t;
- cin >> t;
- while (t--) {
- solve();
- }
- finish;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement