Given an N X M matrix, where ai, j = 1 denotes the cell is not empty, ai, j = 0 denotes the cell is empty and ai, j = 2, denotes that you are standing at that cell. You can move vertically up or down and horizontally left or right to any cell which is empty. The task is to find the minimum number of steps to reach any boundary edge of the matrix. Print -1 if not possible to reach any of the boundary edges.
Note: There will be only one cell with value 2 in the entire matrix.
Examples:
Input: matrix[] = {1, 1, 1, 0, 1}
{1, 0, 2, 0, 1}
{0, 0, 1, 0, 1}
{1, 0, 1, 1, 0}
Output: 2
Move to the right and then move
upwards to reach the nearest boundary
edge.
Input: matrix[] = {1, 1, 1, 1, 1}
{1, 0, 2, 0, 1}
{1, 0, 1, 0, 1}
{1, 1, 1, 1, 1}
Output: -1
Approach: The problem has been solved in Set-1 using Dynamic Programming. In this article, we will be discussing a method using BFS. Given below are the steps to solve the above problem.
- Find the index of the ‘2’ in the matrix.
- Check if this index is a boundary edge or not, if it is, then no moves are required.
- Insert the index x and index y of ‘2’ in the queue with moves as 0.
- Use a 2-D vis array to mark the visiting positions in the matrix.
- Iterate till the queue is empty or we reach any boundary edge.
- Get the front element(x, y, val = moves) in the queue and mark vis[x][y] as visited. Do all the possible moves(right, left, up and down) possible.
- Re-insert val+1 and their indexes of all the valid moves to the queue.
- If the x and y become the boundary edges any time return val.
- If all the moves are made, and the queue is empty, then it is not possible, hence return -1.
Below is the implementation of the above approach:
CPP
// C++ program to find Minimum steps// to reach any of the boundary// edges of a matrix#include <bits/stdc++.h>using namespace std;#define r 4#define c 5// Function to check validitybool check(int i, int j, int n, int m, int mat[r]){ if (i >= 0 && i < n && j >= 0 && j < m) { if (mat[i][j] == 0) return true; } return false;}// Function to find out minimum stepsint findMinSteps(int mat[r], int n, int m){ int indx, indy; indx = indy = -1; // Find index of only 2 in matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == 2) { indx = i, indy = j; break; } } if (indx != -1) break; } // Push elements in the queue queue<pair<int, pair<int, int> > > q; // Push the position 2 with moves as 0 q.push(make_pair(0, make_pair(indx, indy))); // If already at boundary edge if (check(indx, indy, n, m, mat)) return 0; // Marks the visit bool vis[r]; memset(vis, 0, sizeof vis); // Iterate in the queue while (!q.empty()) { // Get the front of the queue auto it = q.front(); // Pop the first element from the queue q.pop(); // Get the position int x = it.second.first; int y = it.second.second; // Moves int val = it.first; // If a boundary edge if (x == 0 || x == (n - 1) || y == 0 || y == (m - 1)) { return val; } // Marks the visited array vis[x][y] = 1; // If a move is possible if (check(x - 1, y, n, m, mat)) { // If not visited previously if (!vis[x - 1][y]) q.push(make_pair(val + 1, make_pair(x - 1, y))); } // If a move is possible if (check(x + 1, y, n, m, mat)) { // If not visited previously if (!vis[x + 1][y]) q.push(make_pair(val + 1, make_pair(x + 1, y))); } // If a move is possible if (check(x, y + 1, n, m, mat)) { // If not visited previously if (!vis[x][y + 1]) q.push(make_pair(val + 1, make_pair(x, y + 1))); } // If a move is possible if (check(x, y - 1, n, m, mat)) { // If not visited previously if (!vis[x][y - 1]) q.push(make_pair(val + 1, make_pair(x, y - 1))); } } return -1;}// Driver Codeint main(){ int mat[r] = { { 1, 1, 1, 0, 1 }, { 1, 0, 2, 0, 1 }, { 0, 0, 1, 0, 1 }, { 1, 0, 1, 1, 0 } }; cout << findMinSteps(mat, r, c);} |
Java
// Java program to find Minimum steps// to reach any of the boundary// edges of a matriximport java.util.*;class GFG { public static final int R = 4; public static final int C = 5; // Function to check validity public static boolean check(int i, int j, int n, int m, int[][] mat) { if (i >= 0 && i < n && j >= 0 && j < m) { if (mat[i][j] == 0) { return true; } } return false; } // Function to find out minimum steps public static int findMinSteps(int[][] mat, int n, int m) { int indx, indy; indx = indy = -1; // Find index of only 2 in matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == 2) { indx = i; indy = j; break; } } if (indx != -1) { break; } } // Push elements in the queue Queue<int[]> q = new LinkedList<int[]>(); // Push the position 2 with moves as 0 q.add(new int[] { indx, indy, 0 }); // If already at boundary edge if (check(indx, indy, n, m, mat)) { return 0; } // Marks the visit boolean[][] vis = new boolean[n][m]; // Iterate in the queue while (!q.isEmpty()) { // Pop the first element from the queue int[] curr = q.poll(); // Get the position int x = curr[0]; int y = curr[1]; int val = curr[2]; // If a boundary edge if (x == 0 || x == (n - 1) || y == 0 || y == (m - 1)) { return val; } // Marks the visited array vis[x][y] = true; // If a move is possible towards up if (check(x - 1, y, n, m, mat)) { // If not visited previously if (!vis[x - 1][y]) { q.add(new int[] { x - 1, y, val + 1 }); } } // If a move is possible towards down if (check(x + 1, y, n, m, mat)) { // If not visited previously if (!vis[x + 1][y]) { q.add(new int[] { x + 1, y, val + 1 }); } } // If a move is possible towards right if (check(x, y + 1, n, m, mat)) { // If not visited previously if (!vis[x][y + 1]) { q.add(new int[] { x, y + 1, val + 1 }); } } // If a move is possible towards left if (check(x, y - 1, n, m, mat)) { // If not visited previously if (!vis[x][y - 1]) { q.add(new int[] { x, y - 1, val + 1 }); } } } return -1; } // Driver Code public static void main(String[] args) { int[][] mat = { { 1, 1, 1, 0, 1 }, { 1, 0, 2, 0, 1 }, { 0, 0, 1, 0, 1 }, { 1, 0, 1, 1, 0 } }; System.out.println(findMinSteps(mat, R, C)); }}// This code is contributed by Prasad Kandekar(prasad264) |
Python3
# Python3 program to find Minimum steps# to reach any of the boundary# edges of a matrixfrom collections import dequer = 4c = 5# Function to check validitydef check(i, j, n, m, mat): if (i >= 0 and i < n and j >= 0 and j < m): if (mat[i][j] == 0): return True return False# Function to find out minimum stepsdef findMinSteps(mat, n, m): indx = indy = -1; # Find index of only 2 in matrix for i in range(n): for j in range(m): if (mat[i][j] == 2): indx = i indy = j break if (indx != -1): break # Push elements in the queue q = deque() # Push the position 2 with moves as 0 q.append([0, indx, indy]) # If already at boundary edge if (check(indx, indy, n, m, mat)): return 0 # Marks the visit vis=[ [0 for i in range(r)]for i in range(r)] # Iterate in the queue while len(q) > 0: # Get the front of the queue it = q.popleft() #Pop the first element from the queue # Get the position x = it[1] y = it[2] # Moves val = it[0] # If a boundary edge if (x == 0 or x == (n - 1) or y == 0 or y == (m - 1)): return val # Marks the visited array vis[x][y] = 1 # If a move is possible if (check(x - 1, y, n, m, mat)): # If not visited previously if (not vis[x - 1][y]): q.append([val + 1, x - 1, y]) # If a move is possible if (check(x + 1, y, n, m, mat)): # If not visited previously if (not vis[x + 1][y]): q.append([val + 1, x + 1, y]) # If a move is possible if (check(x, y + 1, n, m, mat)): # If not visited previously if (not vis[x][y + 1]): q.append([val + 1, x, y + 1]) # If a move is possible if (check(x, y - 1, n, m, mat)): # If not visited previously if (not vis[x][y - 1]): q.append([val + 1, x, y - 1]) return -1# Driver Codemat = [[1, 1, 1, 0, 1 ], [1, 0, 2, 0, 1 ], [0, 0, 1, 0, 1 ], [1, 0, 1, 1, 0 ] ];print(findMinSteps(mat, r, c))# This code is contributed by mohit kumar 29 |
C#
// C# program to find Minimum steps// to reach any of the boundary// edges of a matrixusing System;using System.Collections.Generic;public class GFG { public static readonly int R = 4; public static readonly int C = 5; // Function to check validity public static bool Check(int i, int j, int n, int m, int[, ] mat) { if (i >= 0 && i < n && j >= 0 && j < m) { if (mat[i, j] == 0) { return true; } } return false; } // Function to find out minimum steps public static int findMinSteps(int[, ] mat, int n, int m) { int indx, indy; indx = indy = -1; // Find index of only 2 in matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i, j] == 2) { indx = i; indy = j; break; } } if (indx != -1) { break; } } // Push elements in the queue Queue<int[]> q = new Queue<int[]>(); // Push the position 2 with moves as 0 q.Enqueue(new int[] { indx, indy, 0 }); // If already at boundary edge if (Check(indx, indy, n, m, mat)) { return 0; } // Marks the visit bool[, ] vis = new bool[n, m]; // Iterate in the queue while (q.Count != 0) { // Get the front of the queue int[] curr = q.Dequeue(); // Get the position int x = curr[0]; int y = curr[1]; // Moves int val = curr[2]; // If a boundary edge if (x == 0 || x == (n - 1) || y == 0 || y == (m - 1)) { return val; } // Marks the visited array vis[x, y] = true; // If a move is possible if (Check(x - 1, y, n, m, mat)) { // If not visited previously if (!vis[x - 1, y]) { q.Enqueue( new int[] { x - 1, y, val + 1 }); } } // If a move is possible if (Check(x + 1, y, n, m, mat)) { // If not visited previously if (!vis[x + 1, y]) { q.Enqueue( new int[] { x + 1, y, val + 1 }); } } // If a move is possible if (Check(x, y + 1, n, m, mat)) { // If not visited previously if (!vis[x, y + 1]) { q.Enqueue( new int[] { x, y + 1, val + 1 }); } } // If a move is possible if (Check(x, y - 1, n, m, mat)) { // If not visited previously if (!vis[x, y - 1]) { q.Enqueue( new int[] { x, y - 1, val + 1 }); } } } return -1; } // Driver Code static public void Main(string[] args) { int[, ] mat = { { 1, 1, 1, 0, 1 }, { 1, 0, 2, 0, 1 }, { 0, 0, 1, 0, 1 }, { 1, 0, 1, 1, 0 } }; Console.WriteLine(findMinSteps(mat, 4, 5)); }}// This code is contributed by Prasad Kandekar(prasad264) |
Javascript
<script>// JavaScript program to find Minimum steps// to reach any of the boundary// edges of a matrixconst r = 4const c = 5// Function to check validityfunction check(i, j, n, m, mat){ if (i >= 0 && i < n && j >= 0 && j < m){ if (mat[i][j] == 0) return true } return false}// Function to find out minimum stepsfunction findMinSteps(mat, n, m){ let indx = -1, indy = -1; // Find index of only 2 in matrix for(let i=0;i<n;i++){ for(let j=0;j<m;j++){ if (mat[i][j] == 2){ indx = i indy = j break } } if (indx != -1){ break } } // Push elements in the queue let q = [] // Push the position 2 with moves as 0 q.push([0, indx, indy]) // If already at boundary edge if (check(indx, indy, n, m, mat)) return 0 // Marks the visit let vis = new Array(r); for(let i=0;i<r;i++){ vis[i] = new Array(r).fill(0); } // Iterate in the queue while(q.length > 0){ // Get the front of the queue let it = q.shift() //Pop the first element from the queue // Get the position let x = it[1] let y = it[2] // Moves let val = it[0] // If a boundary edge if (x == 0 || x == (n - 1) || y == 0 || y == (m - 1)) return val // Marks the visited array vis[x][y] = 1 // If a move is possible if (check(x - 1, y, n, m, mat)){ // If not visited previously if (vis[x - 1][y] == 0) q.push([val + 1, x - 1, y]) } // If a move is possible if (check(x + 1, y, n, m, mat)){ // If not visited previously if (vis[x + 1][y] == 0) q.push([val + 1, x + 1, y]) } // If a move is possible if (check(x, y + 1, n, m, mat)){ // If not visited previously if (vis[x][y + 1] == 0) q.push([val + 1, x, y + 1]) } // If a move is possible if (check(x, y - 1, n, m, mat)){ // If not visited previously if (vis[x][y - 1] == 0) q.push([val + 1, x, y - 1]) } } return -1}// Driver Codelet mat = [[1, 1, 1, 0, 1 ], [1, 0, 2, 0, 1 ], [0, 0, 1, 0, 1 ], [1, 0, 1, 1, 0 ]];document.write(findMinSteps(mat, r, c))// This code is contributed by shinjanpatra</script> |
Output
2
Complexity Analysis:
- Time Complexity: O(N^2)
- Auxiliary Space: O(N^2)
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!
