All submissions for this problem are available.
An old plot of land which was used by the army during war has now to be cleared for army construction purposes. As per the available documents and maps of the plot there were mines planted on that land during war with their locations marked on the map. Now these have to be removed but the problem is that there is no proper idea of the range of the mines. They have to be defused as per a set of old rules step by step but with only one rule implemented in a step as mentioned below in order:
- Any live mine with fewer than two live neighbours is defused by the bomb squad without any danger.
- Any live mine with more than three live neighbours is automatically defused due to overcrowded connections.
- Any live mine with two or three live neighbours stays as it was, unchanged, to the next level.
- Any defused mine with exactly three live neighbours becomes a an explosion prone area.
‘X’ – Live Mine ‘.’ – Defused Mine/ Safe Point
The neighbours of a mine are those which immediately surround it.
The plot is represented by a 2D square matrix. You have to tell after ‘N’ steps what would be the state of the plot.
First line contains an integer T which is the no. of test cases, followed by T test cases.
Each test case has W the size of the plot in the first line followed by N the number of steps. This is followed by the number of mines G further followed by G different coordinates of the position of mine (each pair separated in a different line).
For each combination output a 2D matrix representing the plot of land in its new state (as per the symbols used in the examples).
- 1 ≤ T ≤ 100
- 1 ≤ W ≤ 100
- 1 ≤ N ≤ 1500
Output: ....... ....... ...X... ...X... ...X... ....... .......
|Time Limit:||1 - 3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, RUBY, PHP, NODEJS, HASK, SCALA, D, PERL, WSPC, ICK, PRLG, LISP sbcl, LISP clisp, JS, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.