//{ Driver Code Starts
// Initial template for C++
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
// User function template for C++
void updateAnsArrayIfPathFound(int i, int j, vector<vector<int>> &mat, int n, string dir, string validPath, vector<string> &ans) {
// base cases
if(i == n-1 && j == n-1 && mat[i][j] != 0) {
validPath += dir;
ans.push_back(validPath);
return;
}
if(i < 0 || i >= n || j < 0 || j >= n) return;
if(mat[i][j] == 0) return;
mat[i][j] = 0; // marking the cell as visited/blocked
validPath += dir;
updateAnsArrayIfPathFound(i, j+1, mat, n, "R", validPath, ans);
updateAnsArrayIfPathFound(i+1, j, mat, n, "D", validPath, ans);
updateAnsArrayIfPathFound(i, j-1, mat, n, "L", validPath, ans);
updateAnsArrayIfPathFound(i-1, j, mat, n, "U", validPath, ans);
mat[i][j] = 1; // backtracking, because we had marked it as visited/blocked
}
class Solution{
public:
vector<string> findPath(vector<vector<int>> &m, int n) {
// Your code goes here
vector<string> ans;
string validPath = "";
updateAnsArrayIfPathFound(0, 0, m, n, "", validPath, ans);
if(ans.empty()) return {"-1"};
return ans;
}
};
//{ Driver Code Starts.
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<vector<int>> m(n, vector<int> (n,0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> m[i][j];
}
}
Solution obj;
vector<string> result = obj.findPath(m, n);
sort(result.begin(), result.end());
if (result.size() == 0)
cout << -1;
else
for (int i = 0; i < result.size(); i++) cout << result[i] << " ";
cout << endl;
}
return 0;
}
// } Driver Code Ends
