Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #pragma GCC target ("avx2")
- #pragma GCC optimization ("O3")
- #pragma GCC optimization ("unroll-loops")
- #pragma comment (linker, "/STACK:64000000")
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <cmath>
- #include <random>
- #include <unordered_set>
- #include <set>
- using namespace std;
- const int N = 3e5;
- long long t, x,y, n, r, b, m, lx, rx, ly, ry;
- string s;
- int vis[2002][2002];
- char matr[2002][2002];
- int d[2002][2002];
- void ClearVis() {
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- vis[i][j] = 0;
- }
- }
- }
- void ClearD() {
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- d[i][j] = -1;
- }
- }
- }
- vector<pair <int, int> > cycle, stack;
- vector<int> stolb, strok;
- void FindCyc(int str, int col) {
- pair<int, int> nxt = {str,col};
- while (true) {
- stack.push_back(nxt);
- vis[nxt.first][nxt.second] = 2;
- if (matr[nxt.first][nxt.second] == 'U') {
- nxt.first--;
- }
- else if (matr[nxt.first][nxt.second] == 'D') {
- nxt.first++;
- }
- else if (matr[nxt.first][nxt.second] == 'L') {
- nxt.second--;
- }
- else if (matr[nxt.first][nxt.second] == 'R') {
- nxt.second++;
- }
- if (nxt.first < 0 || nxt.first >= n || nxt.second < 0 || nxt.second >= m) {
- int cnt = 1;
- while (!stack.empty()) {
- d[stack[stack.size() - 1].first][stack[stack.size() - 1].second] = cnt;
- vis[stack[stack.size() - 1].first][stack[stack.size() - 1].second] = 1;
- stack.pop_back();
- cnt++;
- }
- return;
- }
- if (vis[nxt.first][nxt.second] == 1) {
- int cnt = d[nxt.first][nxt.second] + 1;
- while (!stack.empty()) {
- d[stack[stack.size() - 1].first][stack[stack.size() - 1].second] = cnt;
- vis[stack[stack.size() - 1].first][stack[stack.size() - 1].second] = 1;
- stack.pop_back();
- cnt++;
- }
- return;
- }
- if (vis[nxt.first][nxt.second] == 2) {
- cycle.clear();
- while (stack[stack.size() - 1] != nxt) {
- cycle.push_back(stack[stack.size() - 1]);
- stack.pop_back();
- }
- cycle.push_back(stack[stack.size() - 1]);
- stack.pop_back();
- for (int i = 0; i < cycle.size(); i++) {
- d[cycle[i].first][cycle[i].second] = cycle.size();
- vis[cycle[i].first][cycle[i].second] = 1;
- }
- if (stack.empty()) {
- return;
- }
- nxt = stack[stack.size() - 1];
- stack.pop_back();
- }
- }
- return;
- }
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- //freopen("input.txt", "r", stdin);
- cin >> t;
- for (int I = 0; I < t; I++) {
- cin >> n >> m;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- cin >> matr[i][j];
- }
- }
- cycle.reserve(n * m + 1);
- ClearD();
- /*stolb.resize(n);
- strok.resize(m);
- for (int i = 0; i < n; i++) {
- stolb[i] = i;
- }
- for (int i = 0; i < n * 3; i++) {
- int u = rand() % n;
- int v = rand() % n;
- swap(stolb[u], stolb[v]);
- }
- for (int i = 0; i < m; i++) {
- strok[i] = i;
- }
- for (int i = 0; i < m * 3; i++) {
- int u = rand() % m;
- int v = rand() % m;
- swap(strok[u], strok[v]);
- }*/
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- if (!vis[i][j]) {
- stack.clear();
- FindCyc(i, j);
- }
- }
- }
- int mxans = 0, a_i = 0, a_j = 0;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- if (d[i][j] > mxans) {
- mxans = d[i][j];
- a_i = i;
- a_j = j;
- }
- }
- }
- cout << a_i + 1 << " " << a_j + 1 << " " << mxans << "\n";
- ClearVis(); ClearD();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement