#define _CRT_SECURE_NO_WARNINGS #pragma comment(linker, "/stack:16777216") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i) #define REP(i, N) FOR(i, 0, N) #define RREP(i, N) RFOR(i, N, 0) #define FILL(A,value) memset(A,value,sizeof(A)) #define ALL(V) V.begin(), V.end() #define SZ(V) (int)V.size() #define PB push_back #define MP make_pair #define Pi 3.14159265358979 typedef long long Int; typedef unsigned long long UINT; typedef vector VI; typedef pair PII; const int INF = 1000000000; const int MAX = 1024; const int MAX2 = 7000; const int BASE = 1000000000; int n; char A[MAX][MAX]; int dx[] = {0, -1, 0, 1}; int dy[] = {1, 0, -1, 0}; string str[] = {"R", "U", "L", "D"}; int x, y; string res; bool B[MAX*MAX]; bool OK(int x, int y) { return (x >= 0 && y >= 0 && x < n && y < n); } // This method will process cnt operations from cyclic string t void Run(string t, int cnt) { FOR (j,0,cnt) { res += t[j % SZ(t)]; x = x + dx[t[j % SZ(t)] - '0']; y = y + dy[t[j % SZ(t)] - '0']; } } int main() { int T; scanf("%d", &T); FOR (test,0,T) { scanf("%d", &n); FOR (i,0,n) scanf("%s", A[i]); // Lets at first forget about any forbidden cells and travel the N*N board // from (1, 1) with no two consecutive operations that are the same // Some operations sequences // Go to the left string l = "3010"; // Go to the right string r = "3212"; // Go down from the left side string dl = "032"; // Go down from the right sode string dr = "230"; // Go left in the last row (if N%2 = 1) string ll = "103"; // Go right in the last row (if N%2 = 1) string rr = "123"; res = ""; x = 0, y = 0; for (int i = 0; i < n; i += 2) { string t; if ((i/2) % 2 == 0) { if (i == n-1) Run(ll, 3*(n-1)); else { Run(l, 2*n-1); if (i+2 != n) Run(dr, x == i ? 6 : 3); } } else { if (i == n-1) Run(rr, 3*(n-1)); else { Run(r, 2*n-1); if (i+2 != n) Run(dl, x == i ? 6 : 3); } } } // Now what can you simply do is when you hit any forbidden cell, swap the move that caused it with the next one // After that it can be proven that no more than 3 consecutive operations will be the same FILL(B, 0); int pos = 0; x = 0, y = 0; while (pos < SZ(res)) { if (A[x][y] != '.') int xx = x + dx[res[pos] - '0']; int yy = y + dy[res[pos] - '0']; if (A[xx][yy] == '#') { if (pos == SZ(res)-1) { B[pos] = 1; break; } if (((res[pos]-'0')+2) % 4 == (res[pos+1]-'0')) { B[pos] = B[pos+1] = 1; pos += 2; } else swap(res[pos], res[pos+1]); } else { x = xx; y = yy; ++ pos; } } // Output the result string ans = ""; FOR (i,0,SZ(res)) if (B[i] == 0) ans += str[res[i] - '0']; printf("%s\n", ans.c_str()); } return 0; }