### Hackerrank code arena challenges

PROBLEM STATEMENT

You are lost in a dense jungle and it is getting dark. There is at least one path that leads you to the city on the other side but you cannot see anything until you are right in front of it as the trees and bushes obscure the path.

Devise an algorithm that is guaranteed to find the way out. Your goal is to go out of the jungle as fast as you can before it gets dark.

**[Input]**:

Input start with a number N and then the matrix of size N x N filled with S, E, T, and P which is our map. Map contains a single S representing the start point, and single E representing the end point and P representing the path and T representing the Tree.

**[Output]**:

output single integer i.e. minimum number of moves from S to E.

Assumptions:

You can assume that the maps would be in square form and can be up to a maximum size of 30X30. You can move in four directions North East West South.

You can move in any direction when you find P but cannot move to a point where a T is present.

*Problem provided by JDASAMPLE INPUT

5 S P P P P T P T P P T P P P P P T E T T P T P T T

SAMPLE OUTPUT

5

**Time Limit: **5.0 sec(s) for each input file.**Memory Limit: **256 MB**Source Limit: **1024 KB

Solution in cpp :

Basically you need the shortest path using BFS starting from start position to end position.

include

using namespace std;

int p=0;

struct Point

{

int x;

int y;

};

struct queueNode

{

Point pt; // The cordinates of a cell

int dist; // cell’s distance of from the source

};

bool isValid(int row, int col,int n )

{

return (row >= 0) && (row < n) &&
(col >= 0) && (col < n);

}

int rowNum[] = {-1, 0, 0, 1};

int colNum[] = {0, -1, 1, 0};

int BFS(int **mat, Point src, Point dest ,int n)

{

if (!mat[src.x][src.y] || !mat[dest.x][dest.y])

return -1;

bool visited[n][n];

}

// Driver program to test above function

int main()

{

int n ;

cin >> n;

p=n;

char mat1[n][n];

//int mat[n][n];

for(int i =0 ; i < n ; i++)
{
for(int j =0 ; j < n ; j++){
cin >> mat1[i][j];

}

}

bool visited[n][n];

memset(visited, false, sizeof visited);

visited[src.x][src.y] = true;

queue q;

queueNode s = {src, 0};

q.push(s); // Enqueue source cell

while (!q.empty())

{

queueNode curr = q.front();

Point pt = curr.pt;

if (pt.x == dest.x && pt.y == dest.y)

return curr.dist;

q.pop();

for (int i = 0; i < 4; i++) {

int row = pt.x + rowNum[i]; int col = pt.y + colNum[i];

if (isValid(row, col,n) &&

mat[row][col] &&

!visited[row][col]) {

visited[row][col] = true; queueNode Adjcell = { {row, col}, curr.dist + 1 }; q.push(Adjcell); } } }

return -1;

}

### Prison Break

Alfie was a prisoner in mythland. Though Alfie was a witty and intelligent guy.He was confident of escaping prison.After few days of observation,He figured out that the prison consists of (**N×N**) cells.i.e The shape of prison was (**N×N**) matrix. Few of the cells of the prison contained motion detectors.So Alfie planned that while escaping the prison he will avoid those cells containing motion detectors.Yet before executing his plan,Alfie wants to know the total number of unique possible paths which he can take to escape the prison.Initially Alfie is in cell **(1,1)** while the exit of the cell **(N,N)**.

**note**:->Alfie can move in all four direction{ if his current location is **(X,Y)**, he can move to either **(X+1,Y)**, **(X−1,Y)**, **(X,Y+1)**, **(X,Y−1)** }. If the first cell **(1,1)** and the last cell(**N,N**) contain motion detectors,then Alfie can’t break out of the prison.

**INPUT**:

The first line contain number of test cases “** T**“.

**test cases follow.The first line of each test case contains an integer “**

*T***“,(i.e the size of the (**

*N***N×N**) matrix).The next

**lines contain**

*n***space separated values either**

*N***or**

*0***.”**

*1***” represents a cell containing motion detectors.**

*1***OUTPUT**:

output total number of unique possible paths which he can take to escape the prison.

**Constraint**:

1≤T≤20

1≤N≤20

Solution :

*//https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/prison-break-5/*

**public class**CA {

*// Check if cell (x, y) is valid or not*

**private static boolean**isValidCell(

**int**x,

**int**y,

**int**N)

{

**if**(x < 0 || y < 0 || x >= N || y >= N)

**return false**;

**return true**;

}

**private static int**countPaths(

**int**maze[][],

**int**x,

**int**y,

**boolean**visited[][],

**int**count,

**int**N)

{

*// if destination (bottom-rightmost cell) is found,*

*// increment the path count*

**if**(x == N – 1 && y == N – 1 && maze[x][y]!=-1)

{

count++;

**return**count;

}

*// mark current cell as visited*

*visited[x][y] =*

**true**;

maze[0][0]=0;

*// if current cell is a valid and open cell*

**if**(

*isValidCell*(x, y,N) && maze[x][y] == 0)

{

*// go down (x, y) –> (x + 1, y)*

**if**(x + 1 < N && !visited[x + 1][y])

count =

*countPaths*(maze, x + 1, y, visited, count,N);

*// go up (x, y) –> (x – 1, y)*

**if**(x – 1 >= 0 && !visited[x – 1][y])

count =

*countPaths*(maze, x – 1, y, visited, count,N);

*// go right (x, y) –> (x, y + 1)*

**if**(y + 1 < N && !visited[x][y + 1])

count =

*countPaths*(maze, x, y + 1, visited, count,N);

*// go left (x, y) –> (x, y – 1)*

**if**(y – 1 >= 0 && !visited[x][y – 1])

count =

*countPaths*(maze, x, y – 1, visited, count,N);

}

*// backtrack from current cell and remove it from current path*

*visited[x][y] =*

**false**;

**return**count;

}

**public static void**main (String[] args)

**throws**java.lang.Exception

{

java.io.BufferedReader r =

**new**java.io.BufferedReader (

**new**java.io.InputStreamReader (System.

**));**

*in*Long t1 =Long.

*parseLong*(r.readLine().toString());

Long max , min;

**while**(t1– > 0) {

Long n =Long.

*parseLong*(r.readLine().toString());

**int**[][] maze =

**new int**[ n.intValue()][n.intValue()];

**for**(

**int**i=0 ; i < n ; i++)

{

**int**j=0;

String data[] = r.readLine().split(

**” “**, n.intValue());

**for**(

**int**k=0 ;k < n ;k++) {

maze[i][k] = Integer.

*parseInt*(data[k].trim())==1?-1:0;

}

}

**int**count = 0;

maze[0][0]=0;

*// 2D matrix to keep track of cells involved in current path*

**boolean**[][] visited =

**new boolean**[n.intValue()][n.intValue()];

*// start from source cell (0, 0)*

*count =*

*countPaths*(maze, 0, 0, visited, count, n.intValue() );

System.

**.println(count);**

*out*}

}

}