407158: GYM102697 129 Conway's Game of Life
Description
You're play a modified version of Conway's Game of Life on a 2D grid. Each cell on the grid can be represented as three states:
An asterisk, representing a cell that is "alive"
A period, representing a cell that is "dead"
An uppercase X, representing a "barrier".
On each turn, cells change their state depending on the following rules:
1. If the cell is not a barrier and is adjacent to any dead cells, the cell becomes a dead cell
2. If the cell is a barrier, is adjacent to only barriers, and is not on the edge of the board, it becomes a dead cell
Note that in these definitions, "adjacent to" refers to all 8 of the spaces next to a cell, including diagonally. Also note that all of the changes to cells take effect after the current turn, so the order that you apply the operations in doesn't matter.
It can be shown that if played infinitely many times, this (simplified) version of Conway's Game of Life will eventually converge on a single board state, i.e. the board will eventually never change between turns. Given a starting board, figure out the final state of the board if played infinitely many times.
InputThe first line of input contains two positive integers $$$n$$$ and $$$m$$$: the number of rows and columns, respectively. The next $$$n$$$ lines each contain $$$m$$$ characters, each representing a cell of the board, according to the rules above.
OutputOutput a $$$n$$$ by $$$m$$$ board in the same format as the input: the final state of the board, after running the algorithm infinitely many times.
ExamplesInput6 6 *****X ****XX **XXX. **XXX. **XXX. XXX..*Output
*****X ****XX **XXX. **X.X. **XXX. XXX...Input
6 6 *****X *.**XX **XXX. **XXX. **XX.. XXX...Output
.....X ....XX ..XXX. ..XXX. ..XX.. XXX...Input
3 4 XXXX XXXX XXXXOutput
XXXX X..X XXXX