Task 3:

Purple vs Brown is a game played on a 2D grid that in theory can be infinite (in our case we will assume that x <= y < 1 000).

Each cell on this grid can be either Purple (represented by 1) or Brown (represented by 0) The game always receives an initial state of the grid which we will call “Generation Zero”. After that, a set of 4 rules are applied across the grid and those rules form the next generation.

Rules that create the next generation:

1. Each Brown cell surrounded by exactly 3 or exactly 6 Purple cells will also become Purple in the next generation.

2. A Brown cell will stay Brown in the next generation if it has either 0, 1, 2, 4, 5, 7 or 8 Purple neighbors.

3. Each Purple cell surrounded by 0, 1, 4, 5, 7 or 8 Purple neighbors will become Brown in the next generation.

4. A Purple cell will stay Purple in the next generation if it has either 2, 3 or 6 Purple neighbors.



Important facts:
- Each cell can be surrounded by up to 8 cells 4 on the sides and 4 on the corners. Exceptions are the corners and the side of the grid.
- All the 4 rules apply at the same time for the whole grid for the next generation to be formed.



Your Task:
Create a program that accepts:
 - The size of our grid - X, Y (X being the width and Y being the height)
 - Then the next Y lines should contain strings (each string is long X characters) created by O`s and 1`s which will represent the “Generation Zero” state and help us build the grid
 - The last arguments to the program should be coordinates (X1 and Y1) and the number N.



(X1 and Y1) will be coordinates of a cell in the grid We would like to calculate in how many generations from Generation Zero until generation N this cell was Purple. (The calculation should include generation Zero and generation N)



Print your result in the console.



Example 1: 3x3 grid, in the initial state, the second row is all 1s. how many times will the cell (1. 0) (top center) become Purple in 10 turns?



3,3

000

111

000

1,0,10

expected result: 5



Example 2: 4x4 grid. Input:



4,4

1001

1111

0100

1010

2,2,15

expected result: 14



Notes:

Try using the four fundamental OOP principles while solving the tasks, where appropriate.

No frameworks needed, use plain JAVA / C# or any other OOP capable language, without external libraries.

Use only the console for Input and output.

Implement validations of the user input.

Format the code to your preferences to improve readability.

Put comments in the code to improve readability.

Use appropriate and descriptive names when naming variables and functions.

Try avoiding code lines longer than 125 characters.

Use GitHub or BitBucket for VCS.

Start small and iterate to improve your code.