A matrix with different values in each cell is given to us. Our goal is to determine the minimal set of locations in the matrix that can be used to traverse the complete matrix starting from those positions.

We can traverse the matrix if the following requirements are met:

Only those neighbors with values less than or equal to the current cell's value can be moved. A cell's neighbor is defined as a cell that shares a side with the provided cell.

Example 1

Input

Matrix = [3,3,4]

[1,1,1]

[1,2,1]

Output

0 2

2 1

Explanation

If we start from (0,2) we can cover 5 vertices in the order (0, 2) -> (0,1) -> (0, 0) -> (1, 0) -> (2, 0) . We cannot cover the entire matrix with this vertex. Remaining vertices can be covered by starting with (2,1) in order (2, 1) -> (1, 1) -> (1, 2) -> (2,2).

Approach

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.

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

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.

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.

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.