Cracked Screen

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

You've been using the same computer for over a decade, and the screen has collected many cracks throughout the years. However, what infuriates you even more is the fact that the cracks aren't symmetrical!

Your screen can be modelled as a N by M grid, where each cell is either # if it's cracked or . if it isn't. You are willing to add some cracks to your screen until it's both vertically and horizontally symmetrical. Formally, in the output, every cell (r, c) must have the same value as the cell (N - r + 1, M) and the cell (N, M - c + 1).

Obviously, to minimize destruction to your screen, you would like to minimize the number of cracks you make. Please find the minimum number of cracks and output what your screen will look like after.


2 \le N, M \le 1000

N and M are even.

Input Specification

The first line contains two integers, N and M.

Each of the following N lines contains a string of M characters of either # or ..

Output Specification

On the first line, output the minimum number of cracks that you have to make.

Then, output N strings of M characters representing the screen after the cracks.

Sample Input 1

4 6

Sample Output 1



There are no comments at the moment.