콘웨이의 라이프 게임(Game of Life) 은 격자 위에서 세포(셀)들이 살아남고, 죽고, 태어나는 과정을 시뮬레이션하는 0인용 게임이다.

\(N \times M\) 크기의 격자가 주어진다. 각 칸은 살아있는 세포(#) 또는 죽은 세포(.)이다. 한 칸의 이웃은 그 칸과 가로·세로·대각선으로 맞닿은 최대 8개의 칸이며, 격자 바깥의 칸은 모두 죽어있는 것으로 본다(경계는 순환하지 않는다).

현재 세대로부터 다음 한 세대는 모든 칸에 대해 동시에 다음 규칙을 적용해 결정된다.

• 살아있는 칸은 살아있는 이웃이 \(2\)개 또는 \(3\)개이면 다음 세대에도 살아있다. 그렇지 않으면(이웃이 너무 적거나 많으면) 죽는다.

• 죽어있는 칸은 살아있는 이웃이 정확히 \(3\)개이면 다음 세대에 새로 태어난다. 그렇지 않으면 계속 죽어있다.

모든 변화는 현재 세대의 상태만을 보고 동시에 일어난다. 즉, 한 칸을 갱신할 때 같은 세대의 다른 칸이 이미 바뀌었다고 생각하면 안 된다.

처음 격자가 주어질 때, 정확히 한 세대 뒤의 격자를 출력하라.

\(1 \le N, M \le 300\)

입력의 각 칸은 # 또는 . 중 하나이다.

첫째 줄에 격자의 크기 \(N\), \(M\) 이 공백으로 구분되어 주어진다 (\(1 \le N, M \le 300\)).

다음 \(N\) 개의 줄에는 각각 길이 \(M\) 의 문자열이 주어지며, 살아있는 세포는 #, 죽은 세포는 . 로 표시된다.

정확히 한 세대가 지난 뒤의 격자를 같은 형식으로 \(N\) 개의 줄에 출력한다. 살아있는 세포는 #, 죽은 세포는 . 로 출력한다.

riseoj 작성

출처 Original