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 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
RESULT: The prisoner is life-imprisoned
_________________________
After All Strides 
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 3 1 3 3 3 3 1 0 0
1 3 3 3 3 3 3 1 0 0
1 1 1 3 2 3 3 1 0 0
0 0 1 3 3 3 3 1 0 0
0 0 1 3 3 3 3 1 0 0
0 0 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
_________________________
Sample 2-D map

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.

Press + to interact
main.cpp
Maps.txt
#include <iostream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
using namespace std;
#define maxRows 100
#define maxCols 100
void 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 here
	return 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:

Press + to interact
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:

  1. Find the prisoner's position.

  2. 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:

Press + to interact
do
{
changeHappen = false;
.
.
  DO_Stride_Forward
  if stride_happens
    changeHappen = 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.

Press + to interact
void prison_BreakSolver(int aPrisonMap[][maxCols], int rows, int cols)
{
    if (isPrisonBreakable(aPrisonMap, rows, cols))
		cout << "Free";
	else
		cout << "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.

Press + to interact
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 proceeded
		for (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);
}
Calculating all approachable strides: Elaborate implementation

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
Prison break level 2