# Hacker Challenge: Prison Break II

Learn how to solve a problem for prison break

The previous lesson discussed the prison break problem with a rectangular wall-shaped room. This lesson discusses a variant of the prison break problem with just one change; the wall could be any irregular polygon.

## The prison break problem 2

The following is the convention we'll follow for the 2-D map:

`0`

represents moveable space.`1`

represents the wall.`2`

represents a prison starting point for the prisoner.`3`

will represent the stride of the prisoner (that will be used while finding the path).

### Example

Below is one example of the 2-D map.

If you click on a number in the widget, all the numbers that are the same will also be highlighted. This helps us view the shape more easily.

=========Example 1=========0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 01 1 1 1 1 1 1 1 0 01 0 1 0 0 0 0 1 0 01 0 0 0 0 0 0 1 0 01 1 1 0 2 0 0 1 0 00 0 1 0 0 0 0 1 0 00 0 1 0 0 0 0 1 0 00 0 1 1 1 1 1 1 0 00 0 0 0 0 0 0 0 0 0RESULT: The prisoner is life-imprisoned_________________________After All Strides0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 01 1 1 1 1 1 1 1 0 01 3 1 3 3 3 3 1 0 01 3 3 3 3 3 3 1 0 01 1 1 3 2 3 3 1 0 00 0 1 3 3 3 3 1 0 00 0 1 3 3 3 3 1 0 00 0 1 1 1 1 1 1 0 00 0 0 0 0 0 0 0 0 0_________________________

The animation below depicts the execution of the above example:

Look at another animation below in which the prisoner can escape:

### Your implementation

Understand the format of `Maps.txt`

and write your code in the widget below.

#include <iostream>#include <iostream>#include <fstream>#include <iomanip>#include <string>using namespace std;#define maxRows 100#define maxCols 100void load2DArray(ifstream &rdr, int aPrisonMap[][maxCols], int &rows, int &cols){// This is exactly like the previous lesson, so we should be// able to write it// Your Implementation}void print2DArray(const char MSG[], int aPrisonMap[][maxCols], int rows, int cols){// This is exactly like the previous lesson, so we should be// able to write it// Your Implementation}bool one_Stride_Forward(int ri, int ci, int aPrisonMap[][maxCols], int rows, int cols, bool &changeHappen){// Write your implmentation here}void calculate_Prisoner_s_Approachable_Strides(int aPrisonMap[][maxCols], int rows, int cols){// Write your implementation here}bool hasPrisoner_ReachBoundary(int aPrisonMap[ ][maxCols], int rows, int cols){// Write your implementation here}bool isPrisonBreakable(int aPrisonMap[][maxCols], int rows, int cols){// Write your implementation here}void prison_BreakSolver(int aPrisonMap[][maxCols], int rows, int cols){// Write your implementation here}int main(){// Write your main herereturn 0;}

### Implementation walkthrough

From here onward, we provide you with a guide on implementing the solution for the prison break problem that you can follow along in the playground above. The guide contains both an explanation and the implementation of the functions. You should look at the solution if you are completely stuck. Best of luck!

#### The `main()`

function

The `main()`

function should be implemented as shown below:

int aPrisonMap[maxRows][maxCols], rows, cols;ifstream rdr("Maps.txt");int noMps;rdr>>noMps;for(int ci=1; ci<=noMps; ci++){load2DArray(rdr, aPrisonMap, rows, cols);print2DArray(("Prison "+to_string(ci)+": ").c_str(), aPrisonMap, rows, cols);prison_BreakSolver(aPrisonMap, rows, cols);print2DArray(("After All Strides "), aPrisonMap, rows, cols);cout <<endl;}

There is nothing changed in the `main()`

function. For simplicity, we have printed the modified 2D array, `aPrisonMap`

, with all the strides saved as `3`

. Also, it is the requirement of the program to print the last modified map.

The only change will be in `prison_BreakSolver()`

. Let's have its algorithmic understanding first.

**Instruction:** Add the above two codes to your playground.

#### Generalized prison break

The initial steps in prison break solver are also the same:

Find the prisoner's position.

There is no need to find the corner room positions of the prison anymore.

Instead, we do the following:

From the prisoner location, we stride in 8 directions, replacing all the empty (wherever there is a

`0`

) neighboring positions of`2`

as`3`

.Then, recurringly, from every location—wherever a stride has been reached—that is

`3`

, we do one stride further. We keep repeating this striding forward process until any further stride is impossible.Iterating recurringly until no possible approachable stride forward is left; how can that be achieved?

That can be maintained in a

`changeHappen`

variable, which will be set to`true`

(as a stride forward is equivalent to changing at least one or many empty values of the`aPrisonMap`

from`0`

to`3`

) if any stride has happened during the exhaustive search on the map. Similarly, in an iteration where no further change in the map happened, the`changeHappen`

variable will remain`false`

, and the loop will end.

The code will look like the following:

do{changeHappen = false;..DO_Stride_Forwardif stride_happenschangeHappen = true; //..}while(changeHappen);

The animation below depicts the execution of one stride:

#### Implementation details of `prison_BreakSolver()`

For detaching the printing part with computation, let's make a function `isPrisonBreakable()`

based on that function decision, we'll print the appropriate output.

void prison_BreakSolver(int aPrisonMap[][maxCols], int rows, int cols){if (isPrisonBreakable(aPrisonMap, rows, cols))cout << "Free";elsecout << "Prisoned for Life...";}

##### Finding out whether the prison is breakable

Given the map in `aPrisonMap`

, this function will have to perform the following two steps:

**STEP 1:** Calculate all the possible strides from the prisoner's position (in this step, we'll replace all the approachable places from `2`

to `3`

).

**STEP 2:** Check if one of the four boundaries (first row, first column, last row, and last column of the map) is approachable by checking the outer boundary values, i.e., if we find even one `3`

on the boundary, the prison is breakable; otherwise, the prisoner is prisoned forever.

bool isPrisonBreakable(int aPrisonMap[][maxCols], int rows, int cols){calculate_Prisoner_s_Approachable_Strides(aPrisonMap, rows, cols);return hasPrisoner_ReachBoundary(aPrisonMap, rows, cols);}

**Instruction:** Add the above two codes to your playground.

##### STEP 1: Calculating all approachable strides

First, create a function, `calculate_Prisoner_s_Approachable_Strides()`

, and do the following:

Inside the function, we'll figure out the prison location first. Once we find the prison location, the

`one_Stride_Forward()`

function will check the prison's left, right, top, bottom, and diagonals and replace the free spaces with`3`

.We have a loop that replaces each side of the prison with

`3`

. In the next iteration, check the first value of`3`

on a map and replace the free sides of the current`3`

with the`3`

using the`one_Stride_Forward()`

function.When do we need to stop this replacement? We have maintained the boolean

`changeHappen`

variable. This variable will remain`true`

whenever any replacement happens on a map. When all replacements have been done`changeHappen`

will be`false`

.The

`one_Stride_Forward()`

function is called by`calculate_Prisoner_s_Approachable_Strides()`

.

void calculate_Prisoner_s_Approachable_Strides(int aPrisonMap[][maxCols], int rows, int cols){// Finding prisoner and doing one stride forward.bool changeHappen;bool found = false;for (int r = 0; r < rows && !found; r++){for (int c = 0; c < cols && !found; c++){if (aPrisonMap[r][c] == 2){one_Stride_Forward(r, c, aPrisonMap, rows, cols, changeHappen);found=true; // both nested loops should break now}}}// Keep striding forward from the already approached locations// until no more stride forward possible.do{changeHappen = false; // resetting so that another striding step// should be proceededfor (int r = 0; r < rows; r++){for (int c = 0; c < cols; c++){if(aPrisonMap[r][c] == 3){one_Stride_Forward(r, c, aPrisonMap, rows, cols,changeHappen) ;// Note: changeHappen is passed by reference}}}}while (changeHappen);}

**Instruction:** Add the above code in the playground.

**One stride forward from a location**

To complete the above implementation, we just need one function now; the `one_Stride_Forward()`

function.

This function will receive the map and a specific coordinate on which it has to stride forward i.e., row and column index; let's call it

`(ri, ci)`

.On the given

`(ri, ci)`

coordinate, this function will stride one time in all 8 neighboring directions (one up, one down, one left and one right, and 4 diagonal positions) of`(ri, ci)`

and only replace free spaces`0`

's with the value`3`

.During this striding, it should also check the boundary conditions—it should not go beyond the map's boundary.

The

`changeHappen`

variable will be set to`true`

if any change happens on the map.

**Instruction:** Add the code to the playground, which should implement the above-mentioned description. If you are stuck, look at the hint below.

##### STEP 2: Figuring out whether prisoner can escape

Let's make the following function, `hasPrisoner_ReachBoundary()`

, in which we'll iterate the first row, the first column, and the last row, the last column. During the iteration, we'll compare each index value with `2`

or `3`

and return `true`

if at least one boundary location is approachable.

**Instruction:** Write the code in the playground, which should do the above-mentioned description. If you are stuck, take a look at the hint.

### Complete implementation of prison break 2

2 10 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 2 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 10 10 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 1 1 0 2 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0