RatMaze_Parth_Cpp

//{ 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