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++
// 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 codeint 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;} |
Java
import java.util.*;public class Main { public static int minOperations(int[][] matrix) { int n = matrix.length; int m = matrix[0].length; Queue<int[]> q = new LinkedList<>(); // vis array int[][] vis = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (matrix[i][j] == 1) { q.offer(new int[] { 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 iterating through the Queue while (!q.isEmpty()) { int[] curr = q.poll(); int t = curr[2]; int Crow = curr[0]; int Ccol = curr[1]; operations = Math.max(operations, t); 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] == 0 && matrix[NewRow][NewCol] == 0) { q.offer(new int[] { 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; } public static void main(String[] args) { 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) System.out.println("-1"); else System.out.println( "The Minimum operations to visit all cells: " + Ans); }} |
Python3
from queue import Queuedef minOperations(Matrix): n = len(Matrix) m = len(Matrix[0]) q = Queue() # vis array vis = [[0 for j in range(m)] for i in range(n)] for i in range(n): for j in range(m): if Matrix[i][j] == 1: q.put(((i, j), 0)) vis[i][j] = 1 else: vis[i][j] = 0 # for all four directions forRow = [-1, 0, 1, 0] forCol = [0, 1, 0, -1] operations = 0 # Start iterating through the Queue while not q.empty(): t = q.queue[0][1] Crow, Ccol = q.queue[0][0] operations = max(operations, t) q.get() for i in range(4): NewRow = Crow + forRow[i] NewCol = Ccol + forCol[i] if NewRow >= 0 and NewRow < n and NewCol >= 0 and NewCol < m and not vis[NewRow][NewCol] and Matrix[NewRow][NewCol] == 0: q.put(((NewRow, NewCol), t+1)) vis[NewRow][NewCol] = 1 for i in range(n): for j in range(m): if vis[i][j] != 1 and Matrix[i][j] == 0: return -1 return operations# Driver codeMatrix = [[1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [2, 2, 0, 0, 0], [0, 0, 0, 0, 0]]Ans = minOperations(Matrix)if Ans == -1: print("-1")else: print("The Minimum operations to visit all cells: ", Ans) |
C#
// C# code for the above approachusing System;using System.Collections.Generic;public class GFG { static int MinOperations(List<List<int> > matrix) { int n = matrix.Count; int m = matrix[0].Count; Queue<Tuple<Tuple<int, int>, int> > q = new Queue<Tuple<Tuple<int, int>, int> >(); // vis array int[, ] vis = new int[n, m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (matrix[i][j] == 1) { q.Enqueue( new Tuple<Tuple<int, int>, int>( new Tuple<int, int>(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 iterating through the Queue while (q.Count > 0) { int t = q.Peek().Item2; int Crow = q.Peek().Item1.Item1; int Ccol = q.Peek().Item1.Item2; operations = Math.Max(operations, t); q.Dequeue(); 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] == 0 && matrix[NewRow][NewCol] == 0) { q.Enqueue( new Tuple<Tuple<int, int>, int>( new Tuple<int, int>(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; } static void Main() { List<List<int> > matrix = new List<List<int> >{ new List<int>{ 1, 0, 0, 0, 0 }, new List<int>{ 0, 0, 0, 0, 0 }, new List<int>{ 2, 2, 0, 0, 0 }, new List<int>{ 0, 0, 0, 0, 0 } }; int ans = MinOperations(matrix); if (ans == -1) Console.WriteLine("-1"); else Console.WriteLine( "The Minimum operations to visit all cells: " + ans); }}// This code is contributed by Susobhan Akhuli |
Javascript
// Javascript code for the above approachfunction minOperations(matrix) { const n = matrix.length; const m = matrix[0].length; const queue = []; // vis array const vis = []; for (let i = 0; i < n; i++) { vis.push([]); for (let j = 0; j < m; j++) { if (matrix[i][j] === 1) { queue.push([{ row: i, col: j }, 0]); vis[i][j] = 1; } else { vis[i][j] = 0; } } } // for all four directions const forRow = [-1, 0, 1, 0]; const forCol = [0, 1, 0, -1]; let operations = 0; // Start iterating through the queue while (queue.length > 0) { const t = queue[0][1]; const { row: crow, col: ccol } = queue[0][0]; operations = Math.max(operations, t); queue.shift(); for (let i = 0; i < 4; i++) { const newRow = crow + forRow[i]; const newCol = ccol + forCol[i]; if ( newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && !vis[newRow][newCol] && matrix[newRow][newCol] === 0 ) { queue.push([{ row: newRow, col: newCol }, t + 1]); vis[newRow][newCol] = 1; } } } for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (vis[i][j] !== 1 && matrix[i][j] === 0) { return -1; } } } return operations;}// Driver codeconst matrix = [ [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [2, 2, 0, 0, 0], [0, 0, 0, 0, 0],];const ans = minOperations(matrix);if (ans === -1) { console.log("-1");} else { console.log("The Minimum operations to visit all cells:", ans);}// This code is contributed by Susobhan Akhuli |
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.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
