To solve this problem, we need to use backtracking we need to find that path that will make us move from source to destination. In order to know which are the cells that are involved in the formation of the path, we need to know either it lies in the path or not, and explore the rest of the four-cell which are connected to it. If the four other cells that are connected to the cell are completely exhausted without reaching the final cell then the current cell is not involved in the path since the other cell could only be reached through the current cell, so we backtrack and consider other possibilities.

In order to avoid cycles in the path, we need to use some boolean matrix vis which will tell us whether we have visited the cell or not. Before moving to any cell we will first check whether it has already visited or not.

We will also create a boolean function issafe which will tell us whether the cell that we are going to visit has its index range within the boundary range or not.

We will follow the given steps:

1. Start from the source cell(0,0) and check if this is the desired cell or not.
2. Mark this cell as visited and check for all the four cells connected to it.
3. If any of the cells are already visited then move to the next cell of the given four directions.
4. If the given parent cell of four directions fails to reach to final destination then make that cell as unmarked.
5. After unmarking that cell backtrack.
6. Repeat the above steps until your recursion function terminates.

Time complexity for the above approach in the worst case is exponential.

Space complexity for the above approach in the worst case is: (N*M) that is the size of the matrix.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//boolean visited array
bool vis[1003][1003];

//matrix to store path values.
ll mat[1003][1003];

//boolean safe function for checking
//index bound range.
bool issafe(ll x, ll y, ll n, ll m)
{
    //if inside index range then return true.
    if (x >= 0 and x < n and y >= 0 and y < m)
        return true;
    else //otherwise return false.
    {
        return false;
    }
}

//void solve function to find the total
//count of the unique path from source to dest.
void solve(ll x, ll y, ll& cnt, ll n, ll m)
{
    //if reached at destination.
    if (x == n - 1 and y == m - 1) {
        //increment count.
        cnt++;
        return;
    }
    //mark visited
    vis[x][y] = true;

    //check for other four direction.
    if (issafe(x, y, n, m) and mat[x][y]) {
        //if move downward  direction.
        if (issafe(x + 1, y, n, m) and vis[x + 1][y] == false) {
            solve(x + 1, y, cnt, n, m);
        }
        //if move in upward directon.
        if (issafe(x - 1, y, n, m) and vis[x - 1][y] == false)
            solve(x - 1, y, cnt, n, m);

        //if move in rightward direction.
        if (issafe(x, y + 1, n, m) and vis[x][y + 1] == false) {
            solve(x, y + 1, cnt, n, m);
        }
        //if move in leftward direction.
        if (issafe(x, y - 1, n, m) and vis[x][y - 1] == false)
            solve(x, y - 1, cnt, n, m);
    }
    //unmark the current cell as it failed to
    //be in the path from source to destination
    //and for backtracking.
    vis[x][y] = false;
}

int main()
{
    ll t;
 
    cout << "Enter number of test cases: ";
    cin >> t;
 
    while (t--) {
        memset(vis, false, sizeof(vis));
 
        ll n, m;
        cout << "Enter size of matrix N and M: ";
        cin >> n >> m;
 
        cout << "Enter elements:\n";
        for (ll i = 0; i < n; i++)
            for (ll j = 0; j < m; j++)
                cin >> mat[i][j];
 
        ll cnt = 0;
 
        solve(0, 0, cnt, n, m);
 
        cout << "Total unique paths: ";
        cout << cnt << "\n";
    }
    
    return 0;
}

Output:

Enter number of test cases: 3
Enter size of matrix N and M: 4 4
Enter elements:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Total unique paths: 184
Enter size of matrix N and M: 4 4
Enter elements:
1 1 1 1
1 1 0 1
0 1 0 1
1 1 1 1
Total unique paths: 4
Enter size of matrix N and M: 2 2
Enter elements:
1 0
0 1
Total unique paths: 0