Minimum initial vertices to traverse the whole matrix with given conditions

Algorithm

• Create a vector Cal which stores all the cell values of the matrix
• Sort the vector 
• Start calling dfs call from the maximum cell value that is at the end of the Cal vector.
• Before doing the dfs call, print the value of the starting cell index
• Create a visited matrix of the same size as that of the given matrix, and after visiting every cell, make that cell true in the visited matrix.
• In every dfs call handle base case to move in all four directions that are left right top and down, the condition to move neighbor is that if the neighbor cell value is less than or equal to current cell value.

Code:

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

// dfs  call to find Minimum initial vertices to traverse the whole matrix
void dfs(int currrow, int currcol, bool visited[][100],int matrix[][100], int row, int column)
{

    // Marking the vertex as visited
    visited[currrow][currcol] = 1;

    // If the down neighbor is valid
    if (currrow + 1 < row && matrix[currrow][currcol] >= matrix[currrow + 1][currcol] && !visited[currrow + 1][currcol])
        dfs(currrow + 1,currcol, visited, matrix, row, column);

    // If right neighbor is valid 
    if (currcol + 1 < column && matrix[currrow][currcol] >= matrix[currrow][currcol + 1] && !visited[currrow][currcol + 1])
        dfs(currrow, currcol + 1, visited, matrix, row, column);

    // If up neighbor is valid 
    if (currrow - 1 >= 0 && matrix[currrow][currcol] >= matrix[currrow - 1][currcol] && !visited[currrow - 1][currcol])
        dfs(currrow - 1, currcol, visited, matrix, row, column);

    // If left neighbor is valid 
    if (currcol - 1 >= 0 && matrix[currrow][currcol] >= matrix[currrow][currcol - 1] && !visited[currrow][currcol - 1])
        dfs(currrow, currcol - 1, visited, matrix, row, column);
}

// Find Minimum initial vertices to traverse the whole matrix
void printMinPath(int matrix[][100], int row, int column)
{

    // Vector to store cell values and its indices
    vector<pair<int, pair<int, int> > > Cal;
    for (int i = 0; i < row; i++)
        for (int j = 0; j < column; j++)
            Cal.push_back(make_pair(matrix[i][j],make_pair(i, j)));
    
    // Sorting according to the cell value
    sort(Cal.begin(), Cal.end());

    // Create a visited array
    bool visited[row][100];

    memset(visited, false, sizeof(visited));

    // Try to apply dfs call with maximum cell value
    for (int i = Cal.size()-1; i >=0 ; i--)
    {

        /*
            If the given vertex is not visited
            then include it in the set
        */
        if (!visited[Cal[i].second.first][Cal[i].second.second])
        {

            // Printing the starting vertex
            cout << Cal[i].second.first << " "<< Cal[i].second.second << endl;

            // dfs  call to find Minimum initial vertices to traverse the whole matrix
            dfs(Cal[i].second.first, Cal[i].second.second,visited, matrix, row, column);
        }
    }
}


int main()
{
    int row = 3, column = 3;

    int matrix[row][100] = {{3, 3,4},
                            {1, 1,},
                            {1,2,1}};
    
    // dfs  call to find Minimum initial vertices to traverse the whole matrix
    printMinPath(matrix, row, column);
    return 0;
}

Output:

0 2
2 1

Time Complexity 

O(row * column * log(row * column))

The time complexity to solve the problem "Minimum initial vertices to traverse the whole matrix with given conditions" is O(row * column * log(row * column)). Since we are exploring all the paths and are going to every cell only once, so after the entire implementation, it will cost O(row * column) time complexity. We are storing all the cell values in a new vector of Cal and finally do sorting for it using the inbuilt sort function. Inbuilt sort function cost log(n) time for sorting where n is the size of the array, so in this case, sorting will cost O(row * column * log(row * column)) time complexity.

Space Complexity 

O(row * column)

The space complexity to solve the problem "Minimum initial vertices to traverse the whole matrix with given conditions" is O(row * column). Since we are creating an extra array visited of size row*column, which stores whether the particular cell in the actual matrix is visited or not. Also, we are creating a vector to store all the cell values.

FAQs

1. What is DFS call?
   DFS (depth-first search) is a data structure traversal algorithm that traverses each element in the data structure. It begins with the source node, which can be the root of the tree, the beginning of a string, or a matrix cell. Before visiting its other neighboring notes, we visit its adjacent node (or children) down the path.
    
2. Is there any other way to solve this problem?
   In such types of problems where we have to explore multiple paths, the intitution is always towards dfs or backtracking. We can also solve this problem using a bfs call by pushing the maximum element in the queue and iterating on the neighbor on the given condition, and pushing back it to the queue. 

Key Takeaways

In this blog, we discussed the solution to find Minimum initial vertices to traverse the whole matrix with given conditions along with the solution. We also explored the time and space complexity of the solution.

Check out this problem - Matrix Median

If you want to learn more about Recursion and DFS Algorithm and want to practice some quality questions which require you to excel your preparation a notch higher, then you can visit our Guided Path for arrays on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.