3

Minimum moves to visit Matrix cells

 1 year ago
source link: https://www.geeksforgeeks.org/minimum-moves-to-visit-matrix-cells/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Minimum moves to visit Matrix cells

mdjabir786

Given a matrix of dimension M * N filled with values 0 (Cell that can be visited), 1 (Starting point), and 2 (Cell that cannot be visited), the task is to determine the minimum operations to visit all the cells filled with 0 and valid directions to move are up, down, left, and right. If it is impossible to visit all cells filled with 0, then return -1.

Examples: 

Input: Matrix[R][C] = {{1, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {2, 2, 0, 0, 0}, {0, 0, 0, 0, 0}}
Output: The Minimum operations to visit all cells: 7
Explanation: Initially the Starting Point is at 0, 0 in Matrix.  

  • In 1st operation, we can visit Matrix[0][1] and Matrix[1][0]. In 2nd operation, we can visit Matrix[1][1]  and Matrix[0][2].
  • In 3rd operation, we can visit Matrix[0][3]  and Matrix[1][2]. In 4th operation, we can visit Matrix[0][4]  and Matrix[1][3] and Matrix[1][2].
  • In 5th operation, we can visit Matrix[1][4]  and Matrix[2][3] and Matrix[3][2]. In 6th operation, we can visit Matrix[2][4]  and Matrix[3][4] and Matrix[3][].
  • In 7th operation, we can visit Matrix[3][0] and Matrix[3][4]. The Minimum operations Required to visit all cells is 7.

Input: Matrix[R][C] ={{0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {2, 2, 0, 0, 0}, {0, 0, 0, 0, 0}}
Output: The Minimum operations to visit all cells: 4

Approach: To solve the problem follow the below idea:

The idea is to use Breadth First Search to traverse the matrix starting from cell with value 1 and keep track of the number of operations taken to reach each cell with value 0 and create a bool visited array to keep track of the visited cells.

Below are the steps for the above approach:

  • Initialize two variables n and m to store the size of the matrix and create a queue to store cells to be visited.
  • Create a 2D visited array of the same size as the matrix and initialize all elements to 0.
  • Iterate through the matrix and add the starting cell with value 1 into the queue and mark the cell as visited in the visited array.
  • Run a loop till the queue becomes empty.
  • Dequeue the front element and for each dequeued element, check its neighboring cells in the four directions (up, down, left, right) and add them into the queue if the neighboring cell is valid, the cell has not been visited before and the neighboring cell has a value of 0 and marks the neighboring cell as visited in the visited array and increment operation count.
  • While enqueuing neighboring cells, keep track of the maximum operation count so far that represents the minimum number of steps required to visit all cells with a value of 0.
  • Iterate through the visited array and check if any cell with value 0 was not visited, return -1.
  • Return the maximum operation count as the minimum number of steps required to visit all cells with the value 0.

Below is the implementation for the above approach:

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
int minOperations(vector<vector<int> >& Matrix)
{
int n = Matrix.size();
int m = Matrix[0].size();
queue<pair<pair<int, int>, int> > q;
// vis array
int vis[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (Matrix[i][j] == 1) {
q.push({ {
i,
j,
},
0 });
vis[i][j] = 1;
}
else {
vis[i][j] = 0;
}
}
}
// for all four directions
int forRow[] = { -1, 0, +1, 0 };
int forCol[] = { 0, +1, 0, -1 };
int operations = 0;
// Start iteating through the Queue
while (!q.empty()) {
int t = q.front().second;
int Crow = q.front().first.first;
int Ccol = q.front().first.second;
operations = max(operations, t);
q.pop();
for (int i = 0; i < 4; i++) {
int NewRow = Crow + forRow[i];
int NewCol = Ccol + forCol[i];
if (NewRow >= 0 && NewRow < n && NewCol >= 0
&& NewCol < m && !vis[NewRow][NewCol]
&& Matrix[NewRow][NewCol] == 0) {
q.push({ { NewRow, NewCol }, t + 1 });
vis[NewRow][NewCol] = 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (vis[i][j] != 1 && Matrix[i][j] == 0) {
return -1;
}
}
}
return operations;
}
// Drivers code
int main()
{
vector<vector<int> > Matrix = { { 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 2, 2, 0, 0, 0 },
{ 0, 0, 0, 0, 0 } };
int Ans = minOperations(Matrix);
if (Ans == -1)
cout << "-1" << endl;
else
cout << "The Minimum operations to visit all cells:"
<< Ans << endl;
return 0;
}
Output
The Minimum operations to visit all cells:7

Time Complexity: O( R *C), Each element of the matrix can be inserted into the queue only once so the upper bound of iteration is O(R*C).
Auxiliary Space: O(R*C), To store the elements in a queue.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK