The prison break problem

The prison break problem constitutes a matrix comprising 0s, 1s, and a single entry of 2. The 0 represents moveable space, 1 represents the wall, and 2 represents the prisoner. The prisoner can pass through 0s but not 1s. Solving the prison break problem means figuring out whether the prisoner is trapped inside the room (made up of 1s), and if so, then is there a way out?

For this problem, we assume the following:

  1. The matrix has a lot of moveable space (a lot of 0s).

  2. The matrix contains a rectangular room made up of walls (a shape made of 1s).

  3. The room may not be closed – meaning there may be one or more moveable spaces (0) in the boundary of the rectangular room.

  4. The prisoner (represented by 2) may be inside or outside the room.


Write a program that reads a matrix (from a file) with a max size of 40 x 80 and should print one of the following results:

  1. The prisoner is already free which means that the prisoner is outside the rectangular prison.

  2. The prisoner is trapped forever, meaning that the prisoner is inside the prison, and the walls have no holes.

  3. The prisoner is trapped but can escape — the prisoner is inside the prison, which is breakable (there's at least one hole in the rectangular wall).


Get hands-on with 1200+ tech skills courses.