Minimum jumps to move outside the matrix
Given a grid of size NXN, some of the cells are vacant and some are blocked. We can move to any horizontally or vertically adjacent cell if the cell is vacant. Also, we can jump to a vacant cell in the 5Γ5 area centered at the square we are currently in. Starting from the cell (r1, c1), find the minimum number of jumps to reach cell (r2, c2). A vacant cell is denoted by β.β and a blocked cell is denoted by β#β.
Note: We cannot move outside the grid.
Example:
Input: numRows = 4, numCols = 4, startRow = 2, startCol = 2, endRow = 3, endCol = 3,
grid = { {β.β, β.β, β.β, β.β},
{β.β, β.β, β.β, β.β},
{β.β, β.β, β.β, β.β},
{β.β, β.β, β.β, β.β} };
Output: 0Input: numRows = 4, numCols = 4, startRow = 1, startCol = 1, endRow = 4, endCol = 4
grid = { {β.β, β.β, β#β, β.β},
{β.β, β.β, β#β, β.β},
{β.β, β#β, β.β, β.β},
{β.β, β#β, β.β, β.β} };
Output: 1
Approach:
To idea is to use use Breadth-First Search (BFS) to explore the grid based on the idea of minimizing the number of jumps. The grid can be categorized into regions based on the required number of jumps, such as 0 jumps, 1 jump, and so on.
Start a BFS from the initial cell and enumerating the squares that can be newly reached with a cost of 0. Then, from the squares reached with a cost of 0, identify squares that can be reached by using Move B (jumps) and are not reachable with a cost less than or equal to 0. Continue this process, enumerating squares based on increasing costs.
To optimize the implementation, we can use 01-BFS when the cost of a move is either 0 or 1. This involves using a deque, pushing vertices that can be moved to with a cost of 0 to the front of the deque and vertices that can be moved to with a cost of 1 to the back. This allows for searching in the order of distances.
Itβs essential to note that if a vertex added with a cost of 1 is later added only with a cost of 0, the same vertex may be added twice. Therefore, careful consideration is required during the implementation to avoid such duplications.
Step-by-step appraoch:
- Initializes deque with the starting cell, sets the distance of the starting cell to 0, and starts the BFS.
- Until dequeue is not empty:
- Explore all possible moves from the current cell
- Check if the new cell is within the grid boundaries
- Check if the new cell is vacant
- Check if the move is adjacent and update distance accordingly
- If the move is not adjacent, update distance considering a jump
- Explore all possible moves from the current cell
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; #define ll long long // Check if the given cell coordinates (r, c) are within the // grid boundaries bool isValidCell( int r, int c, int numRows, int numCols) { return r >= 0 && c >= 0 && r < numRows && c < numCols; } // Check if the move represented by (i, j) is a valid // adjacent move bool isAdjacentMove( int i, int j) { return (i == 1 && j == 0) || (i == -1 && j == 0) || (i == 0 && j == 1) || (i == 0 && j == -1); } // Function to calculate distances using Breadth-First // Search (BFS) void calculateDistances(vector<vector< char > >& grid, vector<vector<ll> >& dist, int startRow, int startCol, int numRows, int numCols) { deque<pair< int , int > > dq; dq.push_front({ startRow, startCol }); dist[startRow][startCol] = 0; while (!dq.empty()) { int r = dq.front().first, c = dq.front().second; dq.pop_front(); // Explore all possible moves from the current cell for ( int i = -2; i <= 2; i++) { for ( int j = -2; j <= 2; j++) { int nr = r + i, nc = c + j; // Check if the new cell is within the grid // boundaries if (isValidCell(nr, nc, numRows, numCols)) { // Check if the new cell is vacant if (grid[nr][nc] == '.' ) { // Check if the move is adjacent and // update distance accordingly if (isAdjacentMove(i, j) && dist[nr][nc] > dist[r]) { dist[nr][nc] = dist[r]; dq.push_front({ nr, nc }); } // If the move is not adjacent, // update distance considering a // jump else if (!isAdjacentMove(i, j) && dist[nr][nc] > dist[r] + 1) { dist[nr][nc] = dist[r] + 1; dq.push_back({ nr, nc }); } } } } } } } // Driver code int main() { // Input vector<vector< char > > grid = { { '.' , '.' , '#' , '.' }, { '.' , '.' , '#' , '.' }, { '.' , '#' , '.' , '.' }, { '.' , '#' , '.' , '.' } }; int numRows = 4, numCols = 4, startRow = 1, startCol = 1, endRow = 4, endCol = 4; // Adjusting indices startRow -= 1; startCol -= 1; endRow -= 1; endCol -= 1; vector<vector<ll> > distances(numRows, vector<ll>(numCols, 1e9)); // Calculate distances using BFS calculateDistances(grid, distances, startRow, startCol, numRows, numCols); // Output the result if (distances[endRow][endCol] == 1e9) cout << -1 << "\n"; else cout << distances[endRow][endCol] << "\n"; return 0; } |
Java
import java.util.ArrayDeque; import java.util.Deque; public class ShortestPathBFS { // Check if the given cell coordinates (r, c) are within // the grid boundaries static boolean isValidCell( int r, int c, int numRows, int numCols) { return r >= 0 && c >= 0 && r < numRows && c < numCols; } // Check if the move represented by (i, j) is a valid // adjacent move static boolean isAdjacentMove( int i, int j) { return (i == 1 && j == 0 ) || (i == - 1 && j == 0 ) || (i == 0 && j == 1 ) || (i == 0 && j == - 1 ); } // Function to calculate distances using Breadth-First // Search (BFS) static void calculateDistances( char [][] grid, long [][] dist, int startRow, int startCol, int numRows, int numCols) { Deque< int []> dq = new ArrayDeque<>(); dq.add( new int [] { startRow, startCol }); dist[startRow][startCol] = 0 ; while (!dq.isEmpty()) { int r = dq.peekFirst()[ 0 ]; int c = dq.peekFirst()[ 1 ]; dq.pollFirst(); // Explore all possible moves from the current // cell for ( int i = - 2 ; i <= 2 ; i++) { for ( int j = - 2 ; j <= 2 ; j++) { int nr = r + i; int nc = c + j; // Check if the new cell is within the // grid boundaries if (isValidCell(nr, nc, numRows, numCols)) { // Check if the new cell is vacant if (grid[nr][nc] == '.' ) { // Check if the move is adjacent // and update distance // accordingly if (isAdjacentMove(i, j) && dist[nr][nc] > dist[r]) { dist[nr][nc] = dist[r]; dq.addFirst( new int [] { nr, nc }); } // If the move is not adjacent, // update distance considering a // jump else if (!isAdjacentMove(i, j) && dist[nr][nc] > dist[r] + 1 ) { dist[nr][nc] = dist[r] + 1 ; dq.addLast( new int [] { nr, nc }); } } } } } } } // Driver code public static void main(String[] args) { // Input char [][] grid = { { '.' , '.' , '#' , '.' }, { '.' , '.' , '#' , '.' }, { '.' , '#' , '.' , '.' }, { '.' , '#' , '.' , '.' } }; int numRows = 4 , numCols = 4 , startRow = 1 , startCol = 1 , endRow = 4 , endCol = 4 ; // Adjusting indices startRow -= 1 ; startCol -= 1 ; endRow -= 1 ; endCol -= 1 ; long [][] distances = new long [numRows][numCols]; // Initialize distances to a large value for ( int i = 0 ; i < numRows; i++) { for ( int j = 0 ; j < numCols; j++) { distances[i][j] = ( long ) 1e9; } } // Calculate distances using BFS calculateDistances(grid, distances, startRow, startCol, numRows, numCols); // Output the result if (distances[endRow][endCol] == ( long ) 1e9) System.out.println(- 1 ); else System.out.println(distances[endRow][endCol]); } } |
Python3
# Python Implementation from collections import deque # Check if the given cell coordinates (r, c) are within the # grid boundaries def is_valid_cell(r, c, num_rows, num_cols): return 0 < = r < num_rows and 0 < = c < num_cols # Check if the move represented by (i, j) is a valid # adjacent move def is_adjacent_move(i, j): return (i = = 1 and j = = 0 ) or (i = = - 1 and j = = 0 ) or (i = = 0 and j = = 1 ) or (i = = 0 and j = = - 1 ) # Function to calculate distances using Breadth-First # Search (BFS) def calculate_distances(grid, start_row, start_col, num_rows, num_cols): dq = deque([(start_row, start_col)]) distances = [[ float ( 'inf' )] * num_cols for _ in range (num_rows)] distances[start_row][start_col] = 0 while dq: r, c = dq.popleft() # Explore all possible moves from the current cell for i in range ( - 2 , 3 ): for j in range ( - 2 , 3 ): nr, nc = r + i, c + j # Check if the new cell is within the grid boundaries if is_valid_cell(nr, nc, num_rows, num_cols): # Check if the new cell is vacant if grid[nr][nc] = = '.' : # Check if the move is adjacent and update distance accordingly if is_adjacent_move(i, j) and distances[nr][nc] > distances[r]: distances[nr][nc] = distances[r] dq.appendleft((nr, nc)) # If the move is not adjacent, update distance considering a jump elif not is_adjacent_move(i, j) and distances[nr][nc] > distances[r] + 1 : distances[nr][nc] = distances[r] + 1 dq.append((nr, nc)) return distances # Driver code if __name__ = = "__main__" : # Input grid = [ [ '.' , '.' , '#' , '.' ], [ '.' , '.' , '#' , '.' ], [ '.' , '#' , '.' , '.' ], [ '.' , '#' , '.' , '.' ] ] num_rows, num_cols = 4 , 4 start_row, start_col = 1 , 1 end_row, end_col = 4 , 4 # Adjusting indices start_row - = 1 start_col - = 1 end_row - = 1 end_col - = 1 # Calculate distances using BFS distances = calculate_distances(grid, start_row, start_col, num_rows, num_cols) # Output the result if distances[end_row][end_col] = = float ( 'inf' ): print ( - 1 ) else : print (distances[end_row][end_col]) # This code is contributed by Sakshi |
C#
using System; using System.Collections.Generic; public class Solution { // Check if the given cell coordinates (r, c) are within the // grid boundaries public static bool IsValidCell( int r, int c, int numRows, int numCols) { return r >= 0 && c >= 0 && r < numRows && c < numCols; } // Check if the move represented by (i, j) is a valid // adjacent move public static bool IsAdjacentMove( int i, int j) { return (i == 1 && j == 0) || (i == -1 && j == 0) || (i == 0 && j == 1) || (i == 0 && j == -1); } // Function to calculate distances using Breadth-First // Search (BFS) public static void CalculateDistances( char [][] grid, long [][] dist, int startRow, int startCol, int numRows, int numCols) { Queue<Tuple< int , int >> dq = new Queue<Tuple< int , int >>(); dq.Enqueue( new Tuple< int , int >(startRow, startCol)); dist[startRow][startCol] = 0; while (dq.Count > 0) { Tuple< int , int > current = dq.Dequeue(); int r = current.Item1, c = current.Item2; // Explore all possible moves from the current cell for ( int i = -2; i <= 2; i++) { for ( int j = -2; j <= 2; j++) { int nr = r + i, nc = c + j; // Check if the new cell is within the grid boundaries if (IsValidCell(nr, nc, numRows, numCols)) { // Check if the new cell is vacant if (grid[nr][nc] == '.' ) { // Check if the move is adjacent and update distance accordingly if (IsAdjacentMove(i, j) && dist[nr][nc] > dist[r]) { dist[nr][nc] = dist[r]; dq.Enqueue( new Tuple< int , int >(nr, nc)); } // If the move is not adjacent, update distance considering a jump else if (!IsAdjacentMove(i, j) && dist[nr][nc] > dist[r] + 1) { dist[nr][nc] = dist[r] + 1; dq.Enqueue( new Tuple< int , int >(nr, nc)); } } } } } } } // Driver code public static void Main( string [] args) { // Input char [][] grid = { new char [] { '.' , '.' , '#' , '.' }, new char [] { '.' , '.' , '#' , '.' }, new char [] { '.' , '#' , '.' , '.' }, new char [] { '.' , '#' , '.' , '.' } }; int numRows = 4, numCols = 4, startRow = 1, startCol = 1, endRow = 4, endCol = 4; // Adjusting indices startRow -= 1; startCol -= 1; endRow -= 1; endCol -= 1; long [][] distances = new long [numRows][]; for ( int i = 0; i < numRows; i++) { distances[i] = new long [numCols]; for ( int j = 0; j < numCols; j++) { distances[i][j] = ( long )1e9; } } // Calculate distances using BFS CalculateDistances(grid, distances, startRow, startCol, numRows, numCols); // Output the result if (distances[endRow][endCol] == 1e9) Console.WriteLine(-1); else Console.WriteLine(distances[endRow][endCol]); } } // This code is contributed by rambabuguphka |
Javascript
// Check if the given cell coordinates (r, c) are within the grid boundaries function isValidCell(r, c, numRows, numCols) { return r >= 0 && c >= 0 && r < numRows && c < numCols; } // Check if the move represented by (i, j) is a valid adjacent move function isAdjacentMove(i, j) { return (i === 1 && j === 0) || (i === -1 && j === 0) || (i === 0 && j === 1) || (i === 0 && j === -1); } // Function to calculate distances using Breadth-First Search (BFS) function calculateDistances(grid, dist, startRow, startCol, numRows, numCols) { const dq = []; dq.push([startRow, startCol]); dist[startRow][startCol] = 0; while (dq.length > 0) { const [r, c] = dq.shift(); // Explore all possible moves from the current cell for (let i = -2; i <= 2; i++) { for (let j = -2; j <= 2; j++) { const nr = r + i; const nc = c + j; // Check if the new cell is within the grid boundaries if (isValidCell(nr, nc, numRows, numCols)) { // Check if the new cell is vacant if (grid[nr][nc] === '.' ) { // Check if the move is adjacent and update distance accordingly if (isAdjacentMove(i, j) && dist[nr][nc] > dist[r]) { dist[nr][nc] = dist[r]; dq.unshift([nr, nc]); } // If the move is not adjacent, update distance considering a jump else if (!isAdjacentMove(i, j) && dist[nr][nc] > dist[r] + 1) { dist[nr][nc] = dist[r] + 1; dq.push([nr, nc]); } } } } } } } // Driver code function main() { // Input const grid = [ [ '.' , '.' , '#' , '.' ], [ '.' , '.' , '#' , '.' ], [ '.' , '#' , '.' , '.' ], [ '.' , '#' , '.' , '.' ] ]; const numRows = 4, numCols = 4, startRow = 1, startCol = 1, endRow = 4, endCol = 4; // Adjusting indices const adjustedStartRow = startRow - 1, adjustedStartCol = startCol - 1, adjustedEndRow = endRow - 1, adjustedEndCol = endCol - 1; const distances = Array.from({ length: numRows }, () => Array(numCols).fill(1e9)); // Calculate distances using BFS calculateDistances(grid, distances, adjustedStartRow, adjustedStartCol, numRows, numCols); // Output the result if (distances[adjustedEndRow][adjustedEndCol] === 1e9) { console.log(-1); } else { console.log(distances[adjustedEndRow][adjustedEndCol]); } } // Run the main function main(); |
1
Time Complexity: O(n*m), where n be the number of rows and m be the number of columns in the grid.
Auxiliary Space: O(n*m)
Contact Us