Minimum Distance from Boundary to Target on a 2D Matrix
Given a matrix of size (n*m) and a point βpβ (x, y). The matrix is given in the form of 0βs and 1βs. In one move you can go in any of the four possible directions (up, down, left, or right) inside the boundary of the matrix whose value is 1. The task is to find the minimum number of moves required to reach βpβ, when started from the boundary of the matrix. Print -1 if βpβ can not be reached. Note: All indexing used is zero-based.
Examples:
Input: n = 5, m = 5
0 1 0 0 0
0 1 1 0 0
0 1 1 1 0
0 0 0 1 1
0 0 0 1 0(x, y) = (1, 2)
Output: 2
Explanation: Some possible paths are:
- (4, 3) -> (3, 3) -> (2, 3) -> (2, 2) -> (1, 2). Steps = 4.
- (3, 4) -> (3, 3) -> (2, 3) -> (2, 2) -> (1, 2). Steps = 4.
- (0, 1) -> (1, 1) -> (1, 2). Steps = 2.
And many more. Out of which 2 is the minimum possible steps.
Input: n = 5, m = 5
0 1 0 0 0
0 1 0 0 0
0 1 1 1 0
0 0 0 1 1
0 0 0 1 0(x, y) = (1, 2)
Output: -1
Explanation: Index (1, 2) is already zero so βqβ can never reach to this index hence the output is -1.
Approach: This can be solved with the following idea:
We can do BFS for this problem. Start BFS from the index (x, y) and traverse in all four possible directions. Because we are doing BFS here so the shortest path will which leads out of the bounds of the matrix will appear first hence as soon as it meets stop the BFS and return the answer.
Below are the steps involved in this approach-
- Start the BFS from the index (x, y) with moves as zero.
- Go in all four unvisited directions whose value is 1.
- Increase the moves by one for each BFS call.
- When any index reaches out of the bounds the number of moves till that point is our answer.
See the below code implementation to understand better:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; class Solution { int bfs(vector<vector< int > >& matrix, int & x, int & y) { if (matrix[x][y] == 0) return -1; // Queue for bfs traversal queue<vector< int > > q; int n = matrix.size(), m = matrix[0].size(); q.push({ x, y, 0 }); int ans = -1; vector<vector< int > > visited(n, vector< int >(m, 0)); while (q.size()) { vector< int > v = q.front(); int i = v[0], j = v[1], moves = v[2]; q.pop(); if (i >= n || i < 0 || j >= m || j < 0) { // As soon as p reaches // out of the bounds stop // bfs calls ans = moves; break ; } else { if (visited[i][j]) continue ; visited[i][j] = 1; // Bfs calls in all // possible directions if (i + 1 >= n || matrix[i + 1][j]) q.push({ i + 1, j, moves + 1 }); if (i - 1 < 0 || matrix[i - 1][j]) q.push({ i - 1, j, moves + 1 }); if (j + 1 >= m || matrix[i][j + 1]) q.push({ i, j + 1, moves + 1 }); if (j - 1 < 0 || matrix[i][j - 1]) q.push({ i, j - 1, moves + 1 }); } } return ans; } public : int minMoves(vector<vector< int > >& matrix, int x, int y) { int ans = bfs(matrix, x, y); return (ans >= 1e7) ? -1 : ans - 1; } }; // Driver code int main() { vector<vector< int > > matrix = { { 0, 1, 0, 0, 0 }, { 0, 1, 1, 0, 0 }, { 0, 1, 1, 1, 0 }, { 0, 0, 0, 1, 1 }, { 0, 0, 0, 1, 0 } }; int x = 1, y = 2; Solution obj; // Function call cout << obj.minMoves(matrix, x, y) << endl; return 0; } |
Java
// Java code for the above approach: import java.util.ArrayDeque; import java.util.Queue; class Solution { public int bfs( int [][] matrix, int x, int y) { if (matrix[x][y] == 0 ) { return - 1 ; } // Queue for bfs traversal Queue< int []> q = new ArrayDeque<>(); int n = matrix.length; int m = matrix[ 0 ].length; q.offer( new int []{x, y, 0 }); int ans = - 1 ; int [][] visited = new int [n][m]; while (!q.isEmpty()) { int [] curr = q.poll(); int i = curr[ 0 ]; int j = curr[ 1 ]; int moves = curr[ 2 ]; if (i >= n || i < 0 || j >= m || j < 0 ) { // As soon as p reaches // out of the bounds stop // bfs calls ans = moves; break ; } else { if (visited[i][j] == 1 ) { continue ; } visited[i][j] = 1 ; // Bfs calls in all // possible directions if (i + 1 >= n || matrix[i + 1 ][j] == 1 ) { q.offer( new int []{i + 1 , j, moves + 1 }); } if (i - 1 < 0 || matrix[i - 1 ][j] == 1 ) { q.offer( new int []{i - 1 , j, moves + 1 }); } if (j + 1 >= m || matrix[i][j + 1 ] == 1 ) { q.offer( new int []{i, j + 1 , moves + 1 }); } if (j - 1 < 0 || matrix[i][j - 1 ] == 1 ) { q.offer( new int []{i, j - 1 , moves + 1 }); } } } return ans; } public int minMoves( int [][] matrix, int x, int y) { Solution obj = new Solution(); int ans = obj.bfs(matrix, x, y); return ans >= 1e7 ? - 1 : ans - 1 ; } } // Driver code public class Main { public static void main(String[] args) { int [][] matrix = {{ 0 , 1 , 0 , 0 , 0 }, { 0 , 1 , 1 , 0 , 0 }, { 0 , 1 , 1 , 1 , 0 }, { 0 , 0 , 0 , 1 , 1 }, { 0 , 0 , 0 , 1 , 0 }}; int x = 1 ; int y = 2 ; Solution obj = new Solution(); System.out.println(obj.minMoves(matrix, x, y)); } } |
Python3
# python code for the above approach: from collections import deque class Solution: def bfs( self , matrix, x, y): if matrix[x][y] = = 0 : return - 1 # Queue for BFS traversal q = deque() n = len (matrix) m = len (matrix[ 0 ]) q.append([x, y, 0 ]) ans = - 1 visited = [[ 0 ] * m for _ in range (n)] while q: i, j, moves = q.popleft() if i > = n or i < 0 or j > = m or j < 0 : # As soon as the cell reaches out of bounds, stop BFS ans = moves break else : if visited[i][j]: continue visited[i][j] = 1 # BFS calls in all possible directions if i + 1 > = n or matrix[i + 1 ][j]: q.append([i + 1 , j, moves + 1 ]) if i - 1 < 0 or matrix[i - 1 ][j]: q.append([i - 1 , j, moves + 1 ]) if j + 1 > = m or matrix[i][j + 1 ]: q.append([i, j + 1 , moves + 1 ]) if j - 1 < 0 or matrix[i][j - 1 ]: q.append([i, j - 1 , moves + 1 ]) return ans def minMoves( self , matrix, x, y): obj = Solution() ans = obj.bfs(matrix, x, y) return - 1 if ans > = 1e7 else ans - 1 # Driver code def main(): matrix = [[ 0 , 1 , 0 , 0 , 0 ], [ 0 , 1 , 1 , 0 , 0 ], [ 0 , 1 , 1 , 1 , 0 ], [ 0 , 0 , 0 , 1 , 1 ], [ 0 , 0 , 0 , 1 , 0 ]] x = 1 y = 2 obj = Solution() # Function call print (obj.minMoves(matrix, x, y)) main() |
C#
using System; using System.Collections.Generic; class Solution { private int BFS( int [][] matrix, ref int x, ref int y) { if (matrix[x][y] == 0) return -1; // Queue for BFS traversal Queue< int []> q = new Queue< int []>(); int n = matrix.Length; int m = matrix[0].Length; q.Enqueue( new int [] { x, y, 0 }); int ans = -1; int [][] visited = new int [n][]; for ( int i = 0; i < n; i++) { visited[i] = new int [m]; for ( int j = 0; j < m; j++) { visited[i][j] = 0; } } while (q.Count > 0) { int [] v = q.Dequeue(); int i = v[0], j = v[1], moves = v[2]; if (i >= n || i < 0 || j >= m || j < 0) { // As soon as (x, y) reaches out of bounds, stop BFS ans = moves; break ; } else { if (visited[i][j] == 1) continue ; visited[i][j] = 1; // BFS in all possible directions if (i + 1 >= n || matrix[i + 1][j] == 1) q.Enqueue( new int [] { i + 1, j, moves + 1 }); if (i - 1 < 0 || matrix[i - 1][j] == 1) q.Enqueue( new int [] { i - 1, j, moves + 1 }); if (j + 1 >= m || matrix[i][j + 1] == 1) q.Enqueue( new int [] { i, j + 1, moves + 1 }); if (j - 1 < 0 || matrix[i][j - 1] == 1) q.Enqueue( new int [] { i, j - 1, moves + 1 }); } } return ans; } public int MinMoves( int [][] matrix, int x, int y) { int ans = BFS(matrix, ref x, ref y); return (ans >= 1e7) ? -1 : ans - 1; } } class Program { static void Main() { int [][] matrix = { new int [] { 0, 1, 0, 0, 0 }, new int [] { 0, 1, 1, 0, 0 }, new int [] { 0, 1, 1, 1, 0 }, new int [] { 0, 0, 0, 1, 1 }, new int [] { 0, 0, 0, 1, 0 } }; int x = 1, y = 2; Solution obj = new Solution(); // Function call Console.WriteLine(obj.MinMoves(matrix, x, y)); } } |
Javascript
class Solution { // Function for breadth first search bfs(matrix, x, y) { if (matrix[x][y] === 0) { return -1; } // Queue for bfs traversal const q = []; const n = matrix.length; const m = matrix[0].length; q.push([x, y, 0]); let ans = -1; const visited = Array.from({ length: n }, () => Array(m).fill(0)); while (q.length > 0) { const [i, j, moves] = q.shift(); if (i >= n || i < 0 || j >= m || j < 0) { // As soon as p reaches // out of the bounds stop // bfs calls ans = moves; break ; } else { if (visited[i][j]) { continue ; } visited[i][j] = 1; // Bfs calls in all // possible directions if (i + 1 >= n || matrix[i + 1][j]) { q.push([i + 1, j, moves + 1]); } if (i - 1 < 0 || matrix[i - 1][j]) { q.push([i - 1, j, moves + 1]); } if (j + 1 >= m || matrix[i][j + 1]) { q.push([i, j + 1, moves + 1]); } if (j - 1 < 0 || matrix[i][j - 1]) { q.push([i, j - 1, moves + 1]); } } } return ans; } // Function to find minimum moves minMoves(matrix, x, y) { const obj = new Solution(); const ans = obj.bfs(matrix, x, y); return ans >= 1e7 ? -1 : ans - 1; } } // Test case const matrix = [[0, 1, 0, 0, 0], [0, 1, 1, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 0]]; const x = 1; const y = 2; const obj = new Solution(); console.log(obj.minMoves(matrix, x, y)); |
2
Time Complexity: O(n*m)
Auxiliary Space: O(n*m)