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")
- #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> > stack, cycle;
- void FindCyc(int str, int col) {
- vis[str][col] = 2;
- pair<int, int> nxt = {str,col};
- if (matr[str][col] == 'U') {
- nxt.first--;
- }
- if (matr[str][col] == 'D') {
- nxt.first++;
- }
- if (matr[str][col] == 'L') {
- nxt.second--;
- }
- if (matr[str][col] == 'R') {
- nxt.second++;
- }
- if (nxt.first < 0 || nxt.first >= n || nxt.second < 0 || nxt.second >= m) {
- d[str][col] = 1;
- vis[str][col] = 1;
- return;
- }
- if (vis[nxt.first][nxt.second] == 2) {
- cycle.clear();
- pair<int, int> nxt2 = nxt;
- if (matr[nxt2.first][nxt2.second] == 'U') {
- nxt2.first--;
- }
- else if (matr[nxt2.first][nxt2.second] == 'D') {
- nxt2.first++;
- }
- else if (matr[nxt2.first][nxt2.second] == 'L') {
- nxt2.second--;
- }
- else if (matr[nxt2.first][nxt2.second] == 'R') {
- nxt2.second++;
- }
- while (nxt2 != nxt) {
- cycle.push_back(nxt2);
- if (matr[nxt2.first][nxt2.second] == 'U') {
- nxt2.first--;
- continue;
- }
- if (matr[nxt2.first][nxt2.second] == 'D') {
- nxt2.first++;
- continue;
- }
- if (matr[nxt2.first][nxt2.second] == 'L') {
- nxt2.second--;
- continue;
- }
- if (matr[nxt2.first][nxt2.second] == 'R') {
- nxt2.second++;
- continue;
- }
- }
- cycle.push_back(nxt);
- for (int i = 0; i < cycle.size(); i++) {
- d[cycle[i].first][cycle[i].second] = cycle.size();
- }
- vis[str][col] = 1;
- return;
- }
- if (!vis[nxt.first][nxt.second]) {
- FindCyc(nxt.first, nxt.second);
- }
- if (d[str][col] == -1) {
- d[str][col] = d[nxt.first][nxt.second] + 1;
- }
- vis[str][col] = 1;
- 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];
- }
- }
- ClearD();
- 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