# 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:DExplanation:

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.

- Push the current cell
- 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.

- Find the parent of the ending cell and update the cell

- Iterate until the ending cell

Below is an implementation of the above approach:

## C++

`// C++ program for tha 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;` `}` |

**Output**

D

**Time Complexity: **O(n*m)**Auxiliary Space: **O(n*m)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.