Game of Life Step

Lab Java Advanced 30 points

Read an r×c grid of # (alive) and . (dead). Print the next generation: a live cell with 2 or 3 live neighbours survives, a dead cell with exactly 3 becomes alive, everything else is dead. Edges have fewer neighbours (no wrapping).

Input

r c, then r rows.

Output

The next grid.

Example

Input

5 5
.....
..#..
..#..
..#..
.....

Output

.....
.....
.###.
.....
.....

Sample input available Sample output available

Editor

Java

Hints

Count the 8 neighbours, staying inside the grid.

Build the new grid from the old one - don't update in place.

Solution explanation

Every cell's new state depends on the old grid, so the result is written to a new structure.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt(), c = sc.nextInt();
        char[][] g = new char[r][];
        for (int i = 0; i < r; i++) {
            g[i] = sc.next().toCharArray();
        }
        for (int i = 0; i < r; i++) {
            StringBuilder row = new StringBuilder();
            for (int j = 0; j < c; j++) {
                int live = 0;
                for (int di = -1; di <= 1; di++) {
                    for (int dj = -1; dj <= 1; dj++) {
                        int ni = i + di, nj = j + dj;
                        if ((di != 0 || dj != 0) && ni >= 0 && ni < r && nj >= 0 && nj < c && g[ni][nj] == '#') {
                            live++;
                        }
                    }
                }
                boolean alive = g[i][j] == '#' ? (live == 2 || live == 3) : live == 3;
                row.append(alive ? '#' : '.');
            }
            System.out.println(row);
        }
    }
}

Output

Answer