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

help
1

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.

Link to the tutorial

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) {
            ans.add(move);
            
            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);
    }
}
2

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
3

Means m*n is row and column number?

4

yes