# What is time and space complexity of rat in maze backtracking problem I am confused

I am solving a problem where we need to make code by which rat can start from a point to reach the destination point . Here 0 means block path, 1 means open path. rat can move 4 different sides(down,left,right,up). I understand concept and I understand the solution but not time complexity.

In tutorial they said time complexity of below problem is 4*(nm) & auxiliary space complexity (nm),I cannot understand what is nm? Is this the matrix size, then it should be nn?

Code

``````import java.util.*;

// m is the given matrix and n is the order of matrix
class Solution {
private static void solve(int i, int j, int a[][], int n, ArrayList<String> ans, String move, int vis[][]) {
if (i == n-1 && j == n-1) {

return;
}

// downward
if (i+1 < n && vis[i+1][j] == 0 && a[i+1][j] == 1) {
vis[i][j] = 1;
solve(i+1, j, a, n, ans, move+'D', vis);
vis[i][j] = 0;
}

// left
if (j-1 >= 0 && vis[i][j-1] == 0 && a[i][j-1] == 1) {
vis[i][j] = 1;
solve(i, j-1, a, n, ans, move+'L', vis);
vis[i][j] = 0;
}

// right
if (j+1 < n && vis[i][j+1] == 0 && a[i][j+1] == 1) {
vis[i][j] = 1;
solve(i, j+1, a, n, ans, move+'R', vis);
vis[i][j] = 0;
}

// upward
if (i-1 >= 0 && vis[i-1][j] == 0 && a[i-1][j] == 1) {
vis[i][j] = 1;
solve(i-1, j, a, n, ans, move+'U', vis);
vis[i][j] = 0;
}
}

public static ArrayList<String> findPath(int[][] m, int n) {
int vis[][] = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
vis[i][j] = 0;

ArrayList<String> ans = new ArrayList<>();
if (m[0][0] == 1)
solve(0, 0, m, n, ans, "", vis);

return ans;
}
}

class TUF {
public static void main(String[] args) {
int n = 4;
int[][] a = {{1, 0, 0, 0}, {1, 1, 0, 1}, {1, 1, 0, 0}, {0, 1, 1, 1}};
Solution obj = new Solution();
ArrayList < String > res = obj.findPath(a, n);
if (res.size() > 0) {
for (int i = 0; i < res.size(); i++)
System.out.print(res.get(i) + " ");

System.out.println();
} else
System.out.println(-1);
}
}
``````

the time complexity is 4^(n²). “m * n” is used instead of “n * n”, because the width and height don’t have to be equal.

1 Like

Means m*n is row and column number?

yes