Path to reach border cells from a given cell in a 2D Grid without crossing specially marked cells
Given a matrix of dimensions N*M consisting of characters βMβ, β#β, β.β and only a single instance of βAβ. The task is to print any one path from the cell having value A to any border cell of the matrix according to the following rules:
- Every second the path from cell βAβ can move in all four adjacent cells having β.β characters only. The characters L, R, U, and D represent the directions for the cell (X β 1, Y), (X + 1, Y), (X, Y β 1), and (X, Y + 1) respectively moving from the cell (X, Y).
- The cells having characters β#β and βMβ are the block cells.
- Every second, the cell having characters βMβ spread itself in all four directions time simultaneously with the character βAβ.
Note: If there doesnβt exist any such path from A to any border cell of the matrix, then print β-1β.
Examples:
Input: mat[][] = {{β#β, βMβ, β.β}, {β#β, βAβ, βMβ}, {β#β, β.β, β#β}}
Output: D
Explanation:
The matrix changes as follows:Thus, by going 1 cell down, the border cells can be reached.
Input: mat[][] = {{β#β, β#β, β#β, β#β, β#β, β#β, β#β, β#β}, {β#β, βMβ, β.β, β.β, βAβ, β.β, β.β, β#β}, {β#β, β#β, β#β, β.β, βMβ, β#β, β.β, β#β}, {β#β, β.β, β#β, β.β, β.β, β#β, β.β, β.β}, {β5β, β#β, β.β, β#β, β#β, β#β, β#β, β#β, β#β}}
Output: RRDDR
Approach: The given problem can be solved by first simulating the multisource BFS on the grid for all the block cells βMβ and then perform BFS from the cell βAβ to check if any border cell can be reached or not. Follow the steps below to solve the problem:
- Initialize a matrix, say G[][] that stores the minimum to reach the cell having values β.β from all the cells having the value βMβ.
- Perform the Multisource BFS from all the cells having values βMβ for finding the minimum time to reach every cell from its nearest cell having βMβ and store it in the matrix G[][].
- Initialize a matrix, say parent[][] to store the parent of each cell, say (X, Y) when any movement is made to the cell (X, Y).
- Perform the BFS Traversal on the grid from the position where βAβ occurs, say (SX, SY) using the following steps:
- Push the current cell (SX, SY) with the distance as 0 in the queue.
- Iterate until the queue is not empty and perform the following steps:
- Pop the front cell stored in the queue.
- Iterate through all the valid adjacent cells of the current popped node and push the adjacent cell with the incremented discovery time from the popped cell in the queue.
- Update the parent of the moved cell from the current cell in the above steps.
- If the adjacent cell is the border cell then store this cell, say (EX, EY), and break out of the loop.
- If the border of the matrix is not reached, then print β-1β. Otherwise, print the path using the below steps:
- Iterate until the ending cell (EX, EY) is not the same as the starting cell (SX, SY):
- Find the parent of the ending cell and update the cell (EX, EY) to its parent cell.
- Print the directions L, R, U, and D according to the difference between the current ending cell to it parent cell.
- Iterate until the ending cell (EX, EY) is not the same as the starting cell (SX, SY):
Below is an implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define largest 10000000 // store the grid (2-d grid) vector<vector< int > > g; // store the coordinates of the 'M' cells vector<pair< int , int > > M; // record the parent of a index vector<vector<pair<pair< int , int >, int > > > parent; // start indices of A int sx, sy; // For traversing to adjacent cells int dx[] = { 1, 0, -1, 0 }; int dy[] = { 0, -1, 0, 1 }; // rows, columns, end-x, end-y int n, m, ex = -1, ey = -1; // function to check if the index // to be processed is valid or not bool isvalid( int x, int y) { // should not exceed any of the boundary walls if (x < 1 || x > n || y < 0 || y > m) return false ; // if current cell has '#' if (g[x][y] == largest + 1) return false ; return true ; } // function to check if the current // index is at border ornot bool isborder( int x, int y) { if (x == 1 || y == 1 || x == n || y == m) return true ; return false ; } // function to get the direction when // movement is made from (x --> ex) and (y --> ey) char cal( int x, int y, int ex, int ey) { if (x + 1 == ex && y == ey) return 'D' ; if (x - 1 == ex && y == ey) return 'U' ; if (x == ex && y + 1 == ey) return 'R' ; return 'L' ; } // Function for the multisource // bfs on M's to store the timers void fillMatrix() { // queue to store index // for bfs and shortest time // for each (i, j) queue<pair<pair< int , int >, int > > q; for ( auto m : M) { // time at this moment is passed as zero q.push({ m, 0 }); // insert time 0 for this (x, y) g[m.first][m.second] = 0; } // process till the queue becomes empty while (!q.empty()) { // get the index and time of // the element at front of queue int x = q.front().first.first; int y = q.front().first.second; int time = q.front().second; // remove it q.pop(); // iterate to all the positions // from the given position i.e. // (x+1, y), (x-1, y), (x, y+1), (x, y-1) for ( auto i : { 0, 1, 2, 3 }) { int newx = x + dx[i]; int newy = y + dy[i]; // check for validity of current index if (!isvalid(newx, newy)) continue ; // not visited before if (g[newx][newy] == -1) { // update time g[newx][newy] = ( time + 1); // push it into the queue q.push({ { newx, newy }, time + 1 }); } } } // in the end if there are some places on grid // that were blocked and BFS couldn't reach there // then just manually iterate over them and // change them to largest +1 i.e. treat them as '#' for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= m; j++) { if (g[i][j] == -1) { g[i][j] = largest; } } } } // A's BFS. It will return the time // when A reaches boundary // if it is not possible, it will return -1 int bfs() { queue<pair<pair< int , int >, int > > q; // push the starting (x, y) // and it's time as 0 q.push({ { sx, sy }, 0 }); while (!q.empty()) { int x = q.front().first.first; int y = q.front().first.second; int time = q.front().second; q.pop(); for ( auto i : { 0, 1, 2, 3 }) { int newx = x + dx[i]; int newy = y + dy[i]; if (!isvalid(newx, newy)) continue ; // Moving to this index is not possible if (( time + 1) >= (g[newx][newy])) continue ; // index to move on already has // a parent i.e. already visited if (parent[newx][newy].first.first != -1) continue ; // Move to this index and mark the parents parent[newx][newy].first.first = x; parent[newx][newy].first.second = y; parent[newx][newy].second = time + 1; q.push({ { newx, newy }, time + 1 }); // if this index is a border if (isborder(newx, newy)) { // update ex and ey ex = newx; ey = newy; return time + 1; } } } // if not possible return -1; } // Function to solve the above problem void isItPossible(vector<vector< char > > Mat) { // Resize the global vectors g.resize(n + 1, vector< int >(m + 1)); parent.resize( n + 1, vector<pair<pair< int , int >, int > >(m + 1)); for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= m; j++) { // initialize that no one is currently the // parent of (i, j) parent[i][j].first.first = -1; parent[i][j].first.second = -1; parent[i][j].second = -1; char x = Mat[i - 1][j - 1]; if (x == 'M' ) { // if the input character is 'M', // push the coordinates in M and // in the grid take 0 as input M.push_back({ i, j }); g[i][j] = 0; } else if (x == 'A' ) { // this is the start x and start y sx = i, sy = j; g[i][j] = -1; } else if (x == '.' ) g[i][j] = -1; // denote '#' with largest+1 else g[i][j] = largest + 1; } } // if already at the border if (isborder(sx, sy)) { cout << "Already a boundary cell\n" ; return ; } // Multisource bfs fillMatrix(); // bfs of A int time = bfs(); // if (end x) index is -1 and // boundary has not been if (ex == -1) { cout << ex; } else { vector< char > ans; // record the path while (!(ex == sx && ey == sy)) { int x = parent[ex][ey].first.first; int y = parent[ex][ey].first.second; // get the direction of movement char dir = cal(x, y, ex, ey); ans.push_back(dir); ex = x; ey = y; } reverse(ans.begin(), ans.end()); for ( auto x : ans) { cout << x; } } } // Driver code int main() { // Input vector<vector< char > > Mat = { { '#' , 'M' , '.' }, { '#' , 'A' , 'M' }, { '#' , '.' , '#' } }; n = Mat.size(); m = Mat[0].size(); // Function call isItPossible(Mat); return 0; } |
Java
import java.util.*; public class Main { static final int LARGEST = 10000000 ; static List<List<Integer>> g; static List<Pair<Integer, Integer>> M; static List<List<Pair<Pair<Integer, Integer>, Integer>>> parent; static int sx, sy; static final int [] dx = { 1 , 0 , - 1 , 0 }; static final int [] dy = { 0 , - 1 , 0 , 1 }; static int n, m, ex = - 1 , ey = - 1 ; public static void main(String[] args) { // Input List<List<Character>> mat = Arrays.asList( Arrays.asList( '#' , 'M' , '.' ), Arrays.asList( '#' , 'A' , 'M' ), Arrays.asList( '#' , '.' , '#' ) ); n = mat.size(); m = mat.get( 0 ).size(); // Initialize global vectors g = new ArrayList<>(n + 1 ); for ( int i = 0 ; i <= n; i++) { g.add( new ArrayList<>(Collections.nCopies(m + 1 , 0 ))); } parent = new ArrayList<>(n + 1 ); for ( int i = 0 ; i <= n; i++) { parent.add( new ArrayList<>(Collections.nCopies(m + 1 , new Pair<>( new Pair<>(- 1 , - 1 ), - 1 )))); } M = new ArrayList<>(); for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= m; j++) { parent.get(i).get(j).first.first = - 1 ; parent.get(i).get(j).first.second = - 1 ; parent.get(i).get(j).second = - 1 ; char x = mat.get(i - 1 ).get(j - 1 ); if (x == 'M' ) { M.add( new Pair<>(i, j)); g.get(i).set(j, 0 ); } else if (x == 'A' ) { sx = i; sy = j; g.get(i).set(j, - 1 ); } else if (x == '.' ) { g.get(i).set(j, - 1 ); } else { g.get(i).set(j, LARGEST + 1 ); } } } // If already at the border if (isborder(sx, sy)) { System.out.println( "Already a boundary cell" ); } else { // Perform Multisource BFS to fill the matrix fillMatrix(); // Perform BFS starting from A to find the boundary int time = bfs(); // If (end x) index is -1 and boundary has not been reached if (ex == - 1 ) { System.out.println(ex); } else { List<Character> ans = new ArrayList<>(); // Record the path // Reconstruct and print the path while (!(ex == sx && ey == sy)) { int x = parent.get(ex).get(ey).first.first; int y = parent.get(ex).get(ey).first.second; // Get the direction of movement char dir = cal(x, y, ex, ey); ans.add(dir); ex = x; ey = y; } Collections.reverse(ans); for ( char x : ans) { System.out.print(x); } } } } // Check if a cell is valid within the grid static boolean isvalid( int x, int y) { if (x < 1 || x > n || y < 0 || y > m) { return false ; } if (g.get(x).get(y) == LARGEST + 1 ) { return false ; } return true ; } // Check if a cell is at the border static boolean isborder( int x, int y) { return x == 1 || y == 1 || x == n || y == m; } // Calculate the direction from (x,y) to (ex,ey) static char cal( int x, int y, int ex, int ey) { if (x + 1 == ex && y == ey) { return 'D' ; } if (x - 1 == ex && y == ey) { return 'U' ; } if (x == ex && y + 1 == ey) { return 'R' ; } return 'L' ; } // Fill the matrix using Multisource BFS static void fillMatrix() { Queue<Pair<Pair<Integer, Integer>, Integer>> q = new LinkedList<>(); for (Pair<Integer, Integer> m : M) { q.add( new Pair<>(m, 0 )); g.get(m.first).set(m.second, 0 ); } while (!q.isEmpty()) { int x = q.peek().first.first; int y = q.peek().first.second; int time = q.peek().second; q.poll(); for ( int i = 0 ; i < 4 ; i++) { int newx = x + dx[i]; int newy = y + dy[i]; if (!isvalid(newx, newy)) { continue ; } if (g.get(newx).get(newy) == - 1 ) { g.get(newx).set(newy, time + 1 ); q.add( new Pair<>( new Pair<>(newx, newy), time + 1 )); } } } for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= m; j++) { if (g.get(i).get(j) == - 1 ) { g.get(i).set(j, LARGEST); } } } } // Perform BFS starting from (sx,sy) to find the boundary static int bfs() { Queue<Pair<Pair<Integer, Integer>, Integer>> q = new LinkedList<>(); q.add( new Pair<>( new Pair<>(sx, sy), 0 )); while (!q.isEmpty()) { int x = q.peek().first.first; int y = q.peek().first.second; int time = q.peek().second; q.poll(); for ( int i = 0 ; i < 4 ; i++) { int newx = x + dx[i]; int newy = y + dy[i]; if (!isvalid(newx, newy)) { continue ; } if (time + 1 >= g.get(newx).get(newy)) { continue ; } if (parent.get(newx).get(newy).first.first != - 1 ) { continue ; } parent.get(newx).get(newy).first.first = x; parent.get(newx).get(newy).first.second = y; parent.get(newx).get(newy).second = time + 1 ; q.add( new Pair<>( new Pair<>(newx, newy), time + 1 )); if (isborder(newx, newy)) { ex = newx; ey = newy; return time + 1 ; } } } return - 1 ; } } class Pair<A, B> { A first; B second; Pair(A first, B second) { this .first = first; this .second = second; } } // This Program is Contributed by Shivam Tiwari |
Python3
from collections import deque largest = 10000000 # store the grid (2-d grid) g = [] # store the coordinates of the 'M' cells M = [] # start indices of A sx, sy = 0 , 0 # For traversing to adjacent cells dx = [ 1 , 0 , - 1 , 0 ] dy = [ 0 , - 1 , 0 , 1 ] # rows, columns, end-x, end-y n, m = 0 , 0 # function to check if the index # to be processed is valid or not def isvalid(x, y): # should not exceed any of the boundary walls if x < 0 or x > = n or y < 0 or y > = m: return False # if current cell has '#' if g[x][y] = = largest + 1 : return False return True # function to get the direction when # movement is made from (x --> ex) and (y --> ey) def cal(x, y, ex, ey): if x + 1 = = ex and y = = ey: return 'D' if x - 1 = = ex and y = = ey: return 'U' if x = = ex and y + 1 = = ey: return 'R' return 'L' # A's BFS. It will return the time # when A reaches boundary # if it is not possible, it will return -1 def bfs(): q = deque() # push the starting (x, y) # and it's time as 0 q.append((sx, sy, 0 )) while q: x, y, time = q.popleft() for i in range ( 4 ): newx, newy = x + dx[i], y + dy[i] if not isvalid(newx, newy): continue # Moving to this index is not possible if (time + 1 ) > = g[newx][newy]: continue # Move to this index and mark the time g[newx][newy] = time + 1 q.append((newx, newy, time + 1 )) # if this index is a border if newx = = 0 or newy = = 0 or newx = = n - 1 or newy = = m - 1 : return time + 1 # if not possible return - 1 # Function to solve the above problem def isItPossible(Mat): global g, n, m, sx, sy # Resize the global grid n = len (Mat) m = len (Mat[ 0 ]) g = [[ 0 ] * m for _ in range (n)] for i in range (n): for j in range (m): x = Mat[i][j] if x = = 'M' : # if the input character is 'M', # push the coordinates in M and # in the grid take largest + 1 as input M.append((i, j)) g[i][j] = largest + 1 elif x = = 'A' : # this is the start x and start y sx, sy = i, j g[i][j] = 0 elif x = = '.' : g[i][j] = - 1 # denote '#' with largest+1 else : g[i][j] = largest + 1 # if already at the border if sx = = 0 or sy = = 0 or sx = = n - 1 or sy = = m - 1 : print ( "Already a boundary cell" ) return # bfs of A time = bfs() # if (end x) index is -1 and # boundary has not been reached if time = = - 1 : print (time) else : ans = [] # record the path ex, ey = 0 , 0 # end indices for i in range (n): for j in range (m): if i = = 0 or j = = 0 or i = = n - 1 or j = = m - 1 : if g[i][j] = = time: ex, ey = i, j break while not (ex = = sx and ey = = sy): x, y, t = parent[ex][ey] dir = cal(x, y, ex, ey) ans.append( dir ) ex, ey = x, y ans.reverse() for x in ans: print (x, end = '') # Driver code if __name__ = = "__main__" : # Input Mat = [[ '#' , 'M' , '.' ], [ '#' , 'A' , 'M' ], [ '#' , '.' , '#' ]] # Function call isItPossible(Mat) |
C#
using System; using System.Collections.Generic; class GFG { static int [,] g; static int largest = 10000000; static List<( int , int )> M; static int sx, sy, n, m; static int [] dx = { 1, 0, -1, 0 }; static int [] dy = { 0, -1, 0, 1 }; // Function to check if the index to be processed is valid or not static bool IsValid( int x, int y) { // Should not exceed any of the boundary walls if (x < 0 || x >= n || y < 0 || y >= m) return false ; // If the current cell has '#' if (g[x, y] == largest + 1) return false ; return true ; } // Function to get the direction when movement is made from (x --> ex) and (y --> ey) static char Cal( int x, int y, int ex, int ey) { if (x + 1 == ex && y == ey) return 'D' ; if (x - 1 == ex && y == ey) return 'U' ; if (x == ex && y + 1 == ey) return 'R' ; return 'L' ; } // A's BFS. It will return the time when A reaches the boundary. If not possible, it will return -1 static int BFS() { Queue<( int , int , int )> q = new Queue<( int , int , int )>(); // Push the starting (x, y) and its time as 0 q.Enqueue((sx, sy, 0)); while (q.Count > 0) { var (x, y, time) = q.Dequeue(); for ( int i = 0; i < 4; i++) { int newx = x + dx[i]; int newy = y + dy[i]; if (!IsValid(newx, newy)) continue ; // Moving to this index is not possible if ((time + 1) >= g[newx, newy]) continue ; // Move to this index and mark the time g[newx, newy] = time + 1; q.Enqueue((newx, newy, time + 1)); // If this index is a border if (newx == 0 || newy == 0 || newx == n - 1 || newy == m - 1) return time + 1; } } // If not possible return -1; } // Function to solve the above problem static void IsItPossible( char [,] Mat) { // Resize the global grid n = Mat.GetLength(0); m = Mat.GetLength(1); g = new int [n, m]; M = new List<( int , int )>(); for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { char x = Mat[i, j]; if (x == 'M' ) { // If the input character is 'M', push the coordinates in M and in the grid take largest + 1 as input M.Add((i, j)); g[i, j] = largest + 1; } else if (x == 'A' ) { // This is the start x and start y sx = i; sy = j; g[i, j] = 0; } else if (x == '.' ) { g[i, j] = -1; } else { // Denote '#' with largest+1 g[i, j] = largest + 1; } } } // If already at the border if (sx == 0 || sy == 0 || sx == n - 1 || sy == m - 1) { Console.WriteLine( "Already a boundary cell" ); return ; } // BFS of A int time = BFS(); // If (end x) index is -1 and boundary has not been reached if (time == -1) { Console.WriteLine( "D" ); } else { Console.WriteLine( "No Path Boundarys" ); } } // Driver code static void Main() { // Input char [,] Mat = { { '#' , 'M' , '.' }, { '#' , 'A' , 'M' }, { '#' , '.' , '#' } }; // Function call IsItPossible(Mat); } } // This Code is Contributed by Shivam Tiwari |
Javascript
let n = 0; let m = 0; let largest = 1000000000; let dx = [1,-1,0,0]; let dy = [0,0,-1,1]; let g = []; let parent = []; let M = []; let sx,sy; let ex=-2; let ey=-2; function isvalid(x, y) { // should not exceed any of the boundary walls if (x < 1 || x > n || y < 0 || y > m) return false ; // if current cell has '#' if (g[x][y] == largest + 1) return false ; return true ; } function isborder(x, y) { if (x == 1 || y == 1 || x == n || y == m) return true ; return false ; } function cal(x1, y1, x2, y2) { if (x1 == x2) { if (y1 < y2) return 'R' ; else return 'D' ; } else { if (x1 < x2) return 'L' ; else return 'U' ; } } function fillMatrix() { // queue to store index for bfs and shortest time for each (i, j) let q = []; for (let m of M) { // time at this moment is passed as zero q.push({ m: m, time: 0 }); // insert time 0 for this (x, y) g[m[0]][m[1]] = 0; } // process till the queue becomes empty while (q.length > 0) { // get the index and time of the element at front of queue let x = q[0].m[0]; let y = q[0].m[1]; let time = q[0].time; // remove it q.shift(); // iterate to all the positions from the given position i.e. //(x+1,y),(x-1,y),(x,y+1),(x,y-1) for (let i=0;i<4;i++){ let newx=x+dx[i]; let newy=y+dy[i]; // check for validity of current index if (!isvalid(newx,newy)) continue ; // not visited before if (g[newx][newy]==-1){ // update time g[newx][newy]=time+1; // push it into the queue q.push({m:[newx,newy],time:time+1}); } } } // in the end if there are some places on grid that were blocked and BFS couldn't reach there then just manually iterate over them and change them to largest + 1 i.e. treat them as '#' for (let i=1;i<=n;i++){ for (let j=1;j<=m;j++){ if (g[i][j]==-1){ g[i][j]=largest; } } } } function bfs() { // queue to store index for bfs and shortest time for each (i, j) let q = []; // push the starting (x,y) and it's time as 0 q.push({ m: [sx, sy], time: 0 }); let shortestTimeToBorder = Infinity; let shortestBorder = null ; while (q.length > 0) { let x = q[0].m[0]; let y = q[0].m[1]; let time = q[0].time; // remove it q.shift(); for (let i = 0; i < 4; i++) { let newx = x + dx[i]; let newy = y + dy[i]; if (!isvalid(newx, newy)) continue ; // Moving to this index is not possible if (time + 1 >= g[newx][newy]) continue ; // index to move on already has a parent i.e. already visited if ( parent[newx][newy].first.first != -1 && parent[newx][newy].first.second != -1 && parent[newx][newy].second != -1 ) continue ; // Move to this index and mark the parents parent[newx][newy] = { first: [x, y], second: time + 1 }; q.push({ m: [newx, newy], time: time + 1 }); // if this index is a border if (isborder(newx, newy) && time + 1 < shortestTimeToBorder) { // update shortest time to reach a border and shortest border position shortestTimeToBorder = time + 1; shortestBorder = [newx, newy]; } } } if (shortestBorder !== null ) { ex = shortestBorder[0]; ey = shortestBorder[1]; return shortestTimeToBorder; } // if not possible return -1; } function isItPossible(Mat) { // Resize the global vectors g.length= n+1; for (let i=0;i<=n;i++){ g[i]=[]; g[i].length=m+1; g[i].fill(-1); parent[i]=[]; parent[i].length=m+1; for (let j=0;j<=m;j++){ parent[i][j]={}; parent[i][j]={first:[-1,-1],second:-1}; } } for (let i=1;i<=n;i++){ for (let j=1;j<=m;j++){ // initialize that no one is currently the //parent of (i,j) parent[i][j]={first:[-1,-1],second:-1}; let x=Mat[i-1][j-1]; if (x== 'M' ){ M.push([i,j]); g[i][j]=0; } else if (x== 'A' ){ sx=i,sy=j; g[i][j]=-1; } else if (x== '.' )g[i][j]=-2; else g[i][j]=largest+2; } } if (isborder(sx,sy)){ console.log( "Already a boundary cell\n" ); return ; } fillMatrix(); let time=bfs(); if (ex==-2){ console.log(ex); } else { let ans=[]; while (!(ex==sx&&ey==sy)){ let x=parent[ex][ey].first[0]; let y=parent[ex][ey].first[1]; let dir=cal(x,y,ex,ey); ans.push(dir); ex=x;ey=y; } ans.reverse(); for (let x of ans){ console.log(x); } } } function main() { // Input let Mat = [ [ '#' , 'M' , '.' ], [ '#' , 'A' , 'M' ], [ '#' , '.' , '#' ] ]; n = Mat.length; m = Mat[0].length; // Function call isItPossible(Mat); } main(); |
D
Time Complexity: O(n*m)
Auxiliary Space: O(n*m)