Print all Paths to Escape Out of a Matrix using K Moves

Approach

We can solve this problem using backtracking. We’ll traverse every path length smaller than equal to ‘K’, which ends at the edge of the matrix, i.e., ‘X_cordinate’ or ‘Y_cordinate’ is either zero or ‘N’ or ‘M’ respectively. We’ll store the current path in a temporary vector and backtrack. Let’s see how this backtracking function findPathLenK() will work.

Parameters

1. ‘N’ - Number of Rows in the Matrix.
2. ‘M’ - Number of Columns in the  Matrix.
3. ‘K’ - Maximum length of the path.
4. ‘CURR_X’ - Current x index you are at.
5. ‘CURR_Y’ - Current y index you are at.
6. ‘TEMP’ - Temporary vector to store the path.
7. ‘RESULT’ - Two-dimensional vector to store all the paths.

Working

1. Base Case 1 - If we are out of the bound, return.
2. Base Case 2 - If we are on the edge, i.e., ‘CURR_X = 0  or CURR_Y = 0 or CURR_X = N - 1 or CURR_Y = M - 1, then add the current path in ‘RESULT’.
3. Base Case 3 - If ‘K <= 0’, we know this will give us a longer path, so we’ll return. 
4. Next, we add the current position in the ‘TEMP’ and recurse in all four directions.
5. In the end, we remove the current position from ‘TEMP’.

Let’s code this solution now.

Program

#include <iostream>
#include <vector>
#include <utility>
#include <unordered_set>

using namespace std;

// Initialize a set to store the visited cells.
unordered_set<string> visit;

// Function to print all paths to escape out of a matrix using K moves.
void findPathLenK(int n, int m, int currX, int currY, int k, vector<pair<int, int>> temp, vector<vector<pair<int, int>>> &result)
{
    // If the index is out of range return.
    if (currX < 0 || currY < 0 || currX >= n || currY >= m)
        return;

    // If we are on the boundary then insert the current path and return.
    if (currX == 0 || currY == 0 || currX == n - 1 || currY == m - 1)
    {
        temp.emplace_back(make_pair(currX, currY));
        result.emplace_back(temp);
        return;
    }

    // Create a key of index and mark it as visited.
    string key = to_string(currX) + " " + to_string(currY);

    // If we've visited the cell before, return.
    if (visit.find(key) != visit.end())
    {
        return;
    }

    // If we've exceeded the length 'K', return.
    if (k <= 0)
        return;

    // Mark the current cell as visited.
    visit.insert(key);

    // Insert the current cell in the path.
    temp.emplace_back(make_pair(currX, currY));

    // Recurse in four direction.
    findPathLenK(n, m, currX - 1, currY, k - 1, temp, result);
    findPathLenK(n, m, currX + 1, currY, k - 1, temp, result);
    findPathLenK(n, m, currX, currY - 1, k - 1, temp, result);
    findPathLenK(n, m, currX, currY + 1, k - 1, temp, result);

    // Pop the current cell from the path and remove it from visited cells.
    temp.pop_back();
    visit.erase(key);
}

void printAllPathLenK(int n, int m, int x, int y, int k)
{
    vector<vector<pair<int, int>>> result;
    findPathLenK(n, m, x, y, k, {}, result);
    
    cout << "All Paths to Escape out of the matrix using K moves: [\n";
    for (vector<int> &path : result)
    {
        cout << "[";
        for (int &cell : path)
        {
            cout << "[" << cell.first << ", " << cell.second << "], ";
        }
        cout << "],\n";
    }
    cout << "]\n";
}

int main()
{
    int n, m, x, y, k;
    cout << "Enter the dimensions of the matrix (N, M): ";
    cin >> n >> m;
    cout << "Enter the value of X, Y, K: ";
    cin >> x >> y >> k;
    printAllPathLenK(n, m, x, y, k);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the dimensions of the matrix (N, M): 5 6
Enter the value of X, Y, K: 3 2 3

Output

All paths to escape out of a matrix using K moves: [
[[3, 2], [2, 2], [1, 2], [0, 2], ],
[[3, 2], [2, 2], [2, 1], [2, 0], ],
[[3, 2], [4, 2], ],
[[3, 2], [3, 1], [2, 1], [2, 0], ],
[[3, 2], [3, 1], [4, 1], ],
[[3, 2], [3, 1], [3, 0], ],
[[3, 2], [3, 3], [4, 3], ],
[[3, 2], [3, 3], [3, 4], [4, 4], ],
[[3, 2], [3, 3], [3, 4], [3, 5], ], ]

Time Complexity

O(4 ^ Y), where Y = N + M.

In the function findPathLenK(), we have four recursive calls, and hence the total function calls are 4^Y. Therefore the time complexity = O(4 ^ Y)

Space Complexity

O(N + M). 

The maximum length of the path from any node to the boundary could be ‘N + M’.

And hence in the worst case, there will be only ‘N + M’ function calls in the recursion stack.

Key Takeaways

Backtracking is one of the most important topics when it comes to Graph problems. Although the above problem does not seem like a graph problem, one can consider each cell as a node and each node is connected to its neighbouring nodes, i.e., left, right, up and down via edge. Then we can think of solving this problem using BFS + Backtracking.

Related Article:

• 8 Queens Problem Using Backtracking

I hope you had fun reading this blog. Check other such exciting blogs on Coding Ninjas Studio.

Recommended Problems:

• Unique Paths
• Longest Path Directed Acyclic Graph
• Longest Path In A Tree
   

Coding Ninjas has also released a new mock test series for cracking top tech companies. Please have a look at it as well.

Thanks for reading.