Given a binary matrix mat[][] of dimensions of N * M and pairs of integers src and dest representing source and destination cells respectively, the task is to find the shortest sequence of moves from the given source cell to the destination cell via cells consisting only of 1s. The allowed moves are moving a cell left (L), right (R), up (U), and down (D) (if exists). If no such path exists, then print “-1”. Otherwise, print the sequence of moves.
Examples:
Input: mat[][] = {{‘0’, ‘0’, ‘0’, ‘0’, ‘0’, ‘0’}, {‘0’, ‘1’, ‘1’, ‘1’, ‘1’, ‘0’}, {‘0’, ‘1’, ‘0’, ‘1’, ‘1’, ‘1’}, {‘0’, ‘1’, ‘1’, ‘1’, ‘1’, ‘0’}, {‘0’, ‘0’, ‘0’, ‘0’, ‘0’, ‘0’}}, src = {1, 2}, dest = {2, 4}
Output: LDDRRRU
Explanation:
Following sequence of moves starting from the source cell (1, 2) to the destination cell (2, 4) is the shortest path possible:
(1, 2) -> (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) -> (3, 4) -> (2, 4)
start -> Left -> Down -> Down ->Right -> Right -> Right -> Up
Therefore, the resultant path is LDDRRRRU.Input: mat[][] = {{‘0’, ‘1’, ‘0’, ‘1’}, {‘1’, ‘0’, ‘1’, ‘1’}, {‘1’, ‘1’, ‘1’, ‘1’}, {‘1’, ‘0’, ‘0’, ‘0’}}, src = {0, 3}, dest = {3, 0}
Output: DDLLLD
Approach: The given problem can be solved by performing BFS Traversal on the given matrix from the given source cell to the destination cell.
Follow the steps below to solve the given problem:
- Initialize a queue required to perform BFS Traversal on the given matrix.
- Initialize a boolean matrix, say visited[N][M], used to check whether a given cell is visited or not. Initially, set all indices as false.
- Initialize another matrix, say distance[N][M], that is used to store the shortest distance from the source node to each cell. Initialize it as -1.
- Initialize a string pathMoves as “” to store the path from source to the destination cell.
- Push the source node into the queue with the distance as 0.
- Iterate until the queue is not empty and perform the following steps:
- Pop the front node of the queue, say currentNode.
- Check if the popped node is the destination node or not. If found to be true, then find the path from the destination cell to the source cell using Backtracking.
- Otherwise, insert all the unvisited adjacent cells of the currently popped node with distance as (previous distance + 1). Update the value of distance[currentNode.x][currentNode.y] as (currentDistance + 1).
- After completing the above steps, if the path exists from the given source to the destination cell, then print the path stored in pathMoves as the result. Otherwise, print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define ROW 4#define COL 4// Stores the coordinates// of the matrix cellstruct Point { int x, y;};// Stores coordinates of// a cell and its distancestruct Node { Point pt; int dist;};// Check if the given cell is valid or notbool isValid(int row, int col){ return (row >= 0) && (col >= 0) && (row < ROW) && (col < COL);}// Stores the moves of the directions of adjacent cellsint dRow[] = { -1, 0, 0, 1 };int dCol[] = { 0, -1, 1, 0 };// Function to find the shortest path from the// source to destination in the given matrixvoid pathMoves(char mat[][COL], Point src, Point dest){ // Stores the distance for each // cell from the source cell int d[ROW][COL]; memset(d, -1, sizeof d); // Distance of source cell is 0 d[src.x][src.y] = 0; // Initialize a visited array bool visited[ROW][COL]; memset(visited, false, sizeof visited); // Mark source cell as visited visited[src.x][src.y] = true; // Create a queue for BFS queue<Node> q; // Distance of source cell is 0 Node s = { src, 0 }; // Enqueue source cell q.push(s); // Keeps track of whether // destination is reached or not bool ok = false; // Iterate until queue is not empty while (!q.empty()) { // Deque front of the queue Node curr = q.front(); Point pt = curr.pt; // If the destination cell is // reached, then find the path if (pt.x == dest.x && pt.y == dest.y) { int xx = pt.x, yy = pt.y; int dist = curr.dist; // Assign the distance of // destination to the // distance matrix d[pt.x][pt.y] = dist; // Stores the smallest path string pathmoves = ""; // Iterate until source is reached while (xx != src.x || yy != src.y) { // Append D if (xx > 0 && d[xx - 1][yy] == dist - 1) { pathmoves += 'D'; xx--; } // Append U if (xx < ROW - 1 && d[xx + 1][yy] == dist - 1) { pathmoves += 'U'; xx++; } // Append R if (yy > 0 && d[xx][yy - 1] == dist - 1) { pathmoves += 'R'; yy--; } // Append L if (yy < COL - 1 && d[xx][yy + 1] == dist - 1) { pathmoves += 'L'; yy++; } dist--; } // Reverse the backtracked path reverse(pathmoves.begin(), pathmoves.end()); cout << pathmoves; ok = true; break; } // Pop the start of queue q.pop(); // Explore all adjacent directions for (int i = 0; i < 4; i++) { int row = pt.x + dRow[i]; int col = pt.y + dCol[i]; // If the current cell is valid // cell and can be traversed if (isValid(row, col) && (mat[row][col] == '1' || mat[row][col] == 's' || mat[row][col] == 'd') && !visited[row][col]) { // Mark the adjacent cells as visited visited[row][col] = true; // Enqueue the adjacent cells Node adjCell = { { row, col }, curr.dist + 1 }; q.push(adjCell); // Update the distance // of the adjacent cells d[row][col] = curr.dist + 1; } } } // If the destination // is not reachable if (!ok) cout << -1;}// Driver Codeint main(){ char mat[ROW][COL] = { { '0', '1', '0', '1' }, { '1', '0', '1', '1' }, { '0', '1', '1', '1' }, { '1', '1', '1', '0' } }; Point src = { 0, 3 }; Point dest = { 3, 0 }; pathMoves(mat, src, dest); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{static int ROW;static int COL;// Stores the coordinates// of the matrix cellstatic class Point{ int x, y; Point(int x, int y) { this.x = x; this.y = y; }}// Stores coordinates of// a cell and its distancestatic class Node { Point pt; int dist; Node(Point p, int dist) { this.pt = p; this.dist = dist; }}// Check if the given cell is valid or notstatic boolean isValid(int row, int col){ return (row >= 0) && (col >= 0) && (row < ROW) && (col < COL);}// Stores the moves of the directions// of adjacent cellsstatic int dRow[] = { -1, 0, 0, 1 };static int dCol[] = { 0, -1, 1, 0 };// Function to find the shortest path from the// source to destination in the given matrixstatic void pathMoves(char mat[][], Point src, Point dest){ // Stores the distance for each // cell from the source cell int d[][] = new int[ROW][COL]; for(int dd[] : d) Arrays.fill(dd, -1); // Distance of source cell is 0 d[src.x][src.y] = 0; // Initialize a visited array boolean visited[][] = new boolean[ROW][COL]; // Mark source cell as visited visited[src.x][src.y] = true; // Create a queue for BFS ArrayDeque<Node> q = new ArrayDeque<>(); // Distance of source cell is 0 Node s = new Node(src, 0); // Enqueue source cell q.addLast(s); // Keeps track of whether // destination is reached or not boolean ok = false; // Iterate until queue is not empty while (!q.isEmpty()) { // Deque front of the queue Node curr = q.removeFirst(); Point pt = curr.pt; // If the destination cell is // reached, then find the path if (pt.x == dest.x && pt.y == dest.y) { int xx = pt.x, yy = pt.y; int dist = curr.dist; // Assign the distance of // destination to the // distance matrix d[pt.x][pt.y] = dist; // Stores the smallest path String pathmoves = ""; // Iterate until source is reached while (xx != src.x || yy != src.y) { // Append D if (xx > 0 && d[xx - 1][yy] == dist - 1) { pathmoves += 'D'; xx--; } // Append U if (xx < ROW - 1 && d[xx + 1][yy] == dist - 1) { pathmoves += 'U'; xx++; } // Append R if (yy > 0 && d[xx][yy - 1] == dist - 1) { pathmoves += 'R'; yy--; } // Append L if (yy < COL - 1 && d[xx][yy + 1] == dist - 1) { pathmoves += 'L'; yy++; } dist--; } // Print reverse the backtracked path for(int i = pathmoves.length() - 1; i >= 0; --i) System.out.print(pathmoves.charAt(i)); ok = true; break; } // Pop the start of queue if (!q.isEmpty()) q.removeFirst(); // Explore all adjacent directions for(int i = 0; i < 4; i++) { int row = pt.x + dRow[i]; int col = pt.y + dCol[i]; // If the current cell is valid // cell and can be traversed if (isValid(row, col) && (mat[row][col] == '1' || mat[row][col] == 's' || mat[row][col] == 'd') && !visited[row][col]) { // Mark the adjacent cells as visited visited[row][col] = true; // Enqueue the adjacent cells Node adjCell = new Node( new Point(row, col), curr.dist + 1); q.addLast(adjCell); // Update the distance // of the adjacent cells d[row][col] = curr.dist + 1; } } } // If the destination // is not reachable if (!ok) System.out.println(-1);}// Driver Codepublic static void main(String[] args){ char mat[][] = { { '0', '1', '0', '1' }, { '1', '0', '1', '1' }, { '0', '1', '1', '1' }, { '1', '1', '1', '0' } }; ROW = mat.length; COL = mat[0].length; Point src = new Point(0, 3); Point dest = new Point(3, 0); pathMoves(mat, src, dest);}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approachfrom collections import deque# Stores the coordinates# of the matrix cellclass Point: def __init__(self, xx, yy): self.x = xx self.y = yy# Stores coordinates of# a cell and its distanceclass Node: def __init__(self, P, d): self.pt = P self.dist = d# Check if the given cell is valid or notdef isValid(row, col): return (row >= 0) and (col >= 0) and (row < 4) and (col < 4)# Stores the moves of the directions of adjacent cellsdRow = [-1, 0, 0, 1]dCol = [0, -1, 1, 0]# Function to find the shortest path from the# source to destination in the given matrixdef pathMoves(mat, src, dest): # Stores the distance for each # cell from the source cell d = [[ -1 for i in range(4)] for i in range(4)] # Distance of source cell is 0 d[src.x][src.y] = 0 # Initialize a visited array visited = [[ False for i in range(4)] for i in range(4)] # memset(visited, false, sizeof visited) # Mark source cell as visited visited[src.x][src.y] = True # Create a queue for BFS q = deque() # Distance of source cell is 0 s = Node(src, 0) # Enqueue source cell q.append(s) # Keeps track of whether # destination is reached or not ok = False # Iterate until queue is not empty while (len(q)>0): # Deque front of the queue curr = q.popleft() pt = curr.pt # If the destination cell is # reached, then find the path if (pt.x == dest.x and pt.y == dest.y): xx, yy = pt.x, pt.y dist = curr.dist # Assign the distance of # destination to the # distance matrix d[pt.x][pt.y] = dist # Stores the smallest path pathmoves = "" # Iterate until source is reached while (xx != src.x or yy != src.y): # Append D if (xx > 0 and d[xx - 1][yy] == dist - 1): pathmoves += 'D' xx -= 1 # Append U if (xx < 4 - 1 and d[xx + 1][yy] == dist - 1): pathmoves += 'U' xx += 1 # Append R if (yy > 0 and d[xx][yy - 1] == dist - 1): pathmoves += 'R' yy -= 1 # Append L if (yy < 4 - 1 and d[xx][yy + 1] == dist - 1): pathmoves += 'L' yy += 1 dist -= 1 # Reverse the backtracked path pathmoves = pathmoves[::-1] print(pathmoves, end = "") ok = True break # Pop the start of queue # q.pop() # Explore all adjacent directions for i in range(4): row = pt.x + dRow[i] col = pt.y + dCol[i] # If the current cell is valid # cell and can be traversed if (isValid(row, col) and (mat[row][col] == '1' or mat[row][col] == 's' or mat[row][col] == 'd') and (not visited[row][col])): # Mark the adjacent cells as visited visited[row][col] = True # Enqueue the adjacent cells adjCell = Node( Point(row, col), curr.dist + 1) q.append(adjCell) # Update the distance # of the adjacent cells d[row][col] = curr.dist + 1 # If the destination # is not reachable if (not ok): print(-1)# Driver Codeif __name__ == '__main__': mat =[ ['0', '1', '0', '1'], [ '1', '0', '1', '1'], [ '0', '1', '1', '1'], [ '1', '1', '1', '0']] src = Point(0, 3) dest = Point(3, 0) pathMoves(mat, src, dest)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{static int ROW;static int COL;// Stores the coordinates// of the matrix cellclass Point{ public int x, y;};static Point newPoint(int x, int y){ Point temp = new Point(); temp.x = x; temp.y = y; return temp;}// Stores coordinates of// a cell and its distanceclass Node { public Point pt; public int dist;};static Node newNode(Point p, int dist){ Node temp = new Node(); temp.pt = p; temp.dist = dist; return temp;}// Check if the given cell is valid or notstatic bool isValid(int row, int col){ return (row >= 0) && (col >= 0) && (row < ROW) && (col < COL);}// Stores the moves of the directions// of adjacent cellsstatic int []dRow = { -1, 0, 0, 1 };static int []dCol = { 0, -1, 1, 0 };// Function to find the shortest path from the// source to destination in the given matrixstatic void pathMoves(char [,]mat, Point src, Point dest){ // Stores the distance for each // cell from the source cell int [,]d = new int[ROW, COL]; for(int i = 0; i < ROW; i++) { for(int j = 0; j < COL; j++) d[i, j] = -1; } // Distance of source cell is 0 d[src.x, src.y] = 0; // Initialize a visited array bool [,]visited = new bool[ROW, COL]; // Mark source cell as visited visited[src.x, src.y] = true; // Create a queue for BFS Queue<Node> q = new Queue<Node>(); // Distance of source cell is 0 Node s = newNode(src, 0); // Enqueue source cell q.Enqueue(s); // Keeps track of whether // destination is reached or not bool ok = false; // Iterate until queue is not empty while (q.Count > 0) { // Deque front of the queue Node curr = q.Peek(); q.Dequeue(); Point pt = curr.pt; // If the destination cell is // reached, then find the path if (pt.x == dest.x && pt.y == dest.y) { int xx = pt.x, yy = pt.y; int dist = curr.dist; // Assign the distance of // destination to the // distance matrix d[pt.x,pt.y] = dist; // Stores the smallest path string pathmoves = ""; // Iterate until source is reached while (xx != src.x || yy != src.y) { // Append D if (xx > 0 && d[xx - 1, yy] == dist - 1) { pathmoves += 'D'; xx--; } // Append U if (xx < ROW - 1 && d[xx + 1, yy] == dist - 1) { pathmoves += 'U'; xx++; } // Append R if (yy > 0 && d[xx, yy - 1] == dist - 1) { pathmoves += 'R'; yy--; } // Append L if (yy < COL - 1 && d[xx, yy + 1] == dist - 1) { pathmoves += 'L'; yy++; } dist--; } // Print reverse the backtracked path for(int i = pathmoves.Length - 1; i >= 0; --i) Console.Write(pathmoves[i]); ok = true; break; } // Pop the start of queue if (q.Count > 0) { q.Peek(); q.Dequeue(); } // Explore all adjacent directions for(int i = 0; i < 4; i++) { int row = pt.x + dRow[i]; int col = pt.y + dCol[i]; // If the current cell is valid // cell and can be traversed if (isValid(row, col) && (mat[row, col] == '1' || mat[row, col] == 's' || mat[row, col] == 'd') && !visited[row, col]) { // Mark the adjacent cells as visited visited[row,col] = true; // Enqueue the adjacent cells Node adjCell = newNode(newPoint(row, col), curr.dist + 1); q.Enqueue(adjCell); // Update the distance // of the adjacent cells d[row, col] = curr.dist + 1; } } } // If the destination // is not reachable if (ok == false) Console.Write(-1);}// Driver Codepublic static void Main(){ char [,]mat = { { '0', '1', '0', '1' }, { '1', '0', '1', '1' }, { '0', '1', '1', '1' }, { '1', '1', '1', '0' } }; ROW = mat.GetLength(0); COL = mat.GetLength(0); Point src = newPoint(0, 3); Point dest = newPoint(3, 0); pathMoves(mat, src, dest);}}// This code is contributed by SURENDRA_GANGWAR |
Javascript
<script>// Javascript program for the above approachvar ROW = 0;var COL = 0;// Stores the coordinates// of the matrix cellclass Point{ constructor() { this.x = 0; this.y = 0; }};function newPoint(x, y){ var temp = new Point(); temp.x = x; temp.y = y; return temp;}// Stores coordinates of// a cell and its distanceclass Node { constructor() { this.pt = null; this.dist = 0; }};function newNode(p, dist){ var temp = new Node(); temp.pt = p; temp.dist = dist; return temp;}// Check if the given cell is valid or notfunction isValid(row, col){ return (row >= 0) && (col >= 0) && (row < ROW) && (col < COL);}// Stores the moves of the directions// of adjacent cellsvar dRow = [-1, 0, 0, 1];var dCol = [0, -1, 1, 0];// Function to find the shortest path from the// source to destination in the given matrixfunction pathMoves(mat, src, dest){ // Stores the distance for each // cell from the source cell var d = Array.from(Array(ROW), ()=>Array(COL)); for(var i = 0; i < ROW; i++) { for(var j = 0; j < COL; j++) d[i][j] = -1; } // Distance of source cell is 0 d[src.x][src.y] = 0; // Initialize a visited array var visited = Array.from(Array(ROW), ()=>Array(COL)); // Mark source cell as visited visited[src.x][src.y] = true; // Create a queue for BFS var q = []; // Distance of source cell is 0 var s = newNode(src, 0); // push source cell q.push(s); // Keeps track of whether // destination is reached or not var ok = false; // Iterate until queue is not empty while (q.length > 0) { // Deque front of the queue var curr = q[0]; q.shift(); var pt = curr.pt; // If the destination cell is // reached, then find the path if (pt.x == dest.x && pt.y == dest.y) { var xx = pt.x, yy = pt.y; var dist = curr.dist; // Assign the distance of // destination to the // distance matrix d[pt.x][pt.y] = dist; // Stores the smallest path var pathmoves = ""; // Iterate until source is reached while (xx != src.x || yy != src.y) { // Append D if (xx > 0 && d[xx - 1][yy] == dist - 1) { pathmoves += 'D'; xx--; } // Append U if (xx < ROW - 1 && d[xx + 1][yy] == dist - 1) { pathmoves += 'U'; xx++; } // Append R if (yy > 0 && d[xx][yy - 1] == dist - 1) { pathmoves += 'R'; yy--; } // Append L if (yy < COL - 1 && d[xx][yy + 1] == dist - 1) { pathmoves += 'L'; yy++; } dist--; } // Print reverse the backtracked path for(var i = pathmoves.length - 1; i >= 0; --i) document.write(pathmoves[i]); ok = true; break; } // Pop the start of queue if (q.length > 0) { q.shift(); } // Explore all adjacent directions for(var i = 0; i < 4; i++) { var row = pt.x + dRow[i]; var col = pt.y + dCol[i]; // If the current cell is valid // cell and can be traversed if (isValid(row, col) && (mat[row][col] == '1' || mat[row][col] == 's' || mat[row][col] == 'd') && !visited[row][col]) { // Mark the adjacent cells as visited visited[row][col] = true; // Enqueue the adjacent cells var adjCell = newNode(newPoint(row, col), curr.dist + 1); q.push(adjCell); // Update the distance // of the adjacent cells d[row][col] = curr.dist + 1; } } } // If the destination // is not reachable if (ok == false) document.write(-1);}// Driver Codevar mat = [ [ '0', '1', '0', '1' ], [ '1', '0', '1', '1' ], [ '0', '1', '1', '1' ], [ '1', '1', '1', '0' ] ];ROW = mat.length;COL = mat[0].length;var src = newPoint(0, 3);var dest = newPoint(3, 0);pathMoves(mat, src, dest);// This code is contributed by rutvik_56.</script> |
Output:
DLDLDL
Time Complexity: O(N*M), as we are using nested loops for traversing the matrix.
Auxiliary Space: O(N*M), as we are using extra space for visited matrix.
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!
