In this HackerEarth Prison Break problem solution 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 X N) cells.i.e The shape of prison was (N X 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).


HackerEarth Prison Break problem solution


HackerEarth Prison Break problem solution.

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int cell[20][20],mark[20][20],count_route=0,n;

void route(int i,int j){
if((i==n)&&(j==n)){
count_route++;
return;
}
mark[i][j] = 1;
if( (j+1)<=n && mark[i][j+1] == 0 && cell[i][j+1] == 0 )
route(i,j+1);
if( (i+1)<=n && mark[i+1][j] == 0 && cell[i+1][j] == 0 )
route(i+1,j);
if( (j-1)>=1 && mark[i][j-1] == 0 && cell[i][j-1] == 0 )
route(i,j-1);
if( (i-1)>=1 && mark[i-1][j] == 0 && cell[i-1][j] == 0 )
route(i-1,j);
mark[i][j] = 0;
return;
}

int main()
{
int i,j,t;
cin >> t;
while(t--){
cin >> n;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cin >> cell[i][j];
mark[i][j] = 0;
}
}
count_route = 0;
route(1,1);
cout << count_route << endl;
}
return 0;
}