Problem I
Fake Snowflake
Languages
en
sv
Alexander is a climate change denier and wants to prove to Joshua that the Earth is not getting warmer at all. Alexander argues that it has already snowed several times in November, which suggests that the temperature is dropping. Joshua, who mostly stays indoors, hasn’t noticed any snow. Therefore, Alexander has been running around taking pictures of a lot of particles in the air, hoping to show photographic evidence to Joshua. Now, he has finally taken a picture he is quite satisfied with, but he needs to make some changes before showing the image.
Joshua, who loves fractals and unnecessarily complicated things, has specific ideas about how a snowflake should look. An image consists of $N \times N$ pixels, where $N$ is an odd number, and each pixel is either white or black. The snowflake is made up of the white pixels in the image. According to Joshua, the image represents a snowflake if the following criteria are met:
-
The center pixel is white.
-
If you rotate the image clockwise 90 degrees, it looks the same.
-
If you mirror the image along the vertical centerline, it looks the same.
-
There are no $2 \times 2$ squares consisting entirely of white pixels.
-
The set of white pixels is contiguous without diagonal steps. This means that if you start with a pen on any white pixel, you can access every other white pixel without lifting the pen and without drawing on black pixels. The pen can go up, down, left and right, but not diagonally.
-
The set of black pixels is contiguous with diagonal steps. This means that if you start with a pen on any black pixel, you can access every other black pixel without lifting the pen and without drawing on white pixels. The pen can go up, down, left, right, and diagonally.
-
There are no hooks in the snowflake. Let $\text {pixel}_\text {up}$, $\text {pixel}_\text {right}$, $\text {pixel}_\text {down}$, and $\text {pixel}_\text {left}$ be the adjacent pixels to a white pixel. A hook occurs if exactly two of these adjacent pixels are also white, and they are not on opposite sides of the pixel. For example, if $\text {pixel}_\text {up}$ and $\text {pixel}_\text {right}$ are white while $\text {pixel}_\text {down}$ and $\text {pixel}_\text {left}$ are black, a hook is formed, but if $\text {pixel}_\text {up}$ and $\text {pixel}_\text {down}$ are white and $\text {pixel}_\text {right}$ and $\text {pixel}_\text {left}$ are black, a hook is not formed.
Alexander has downloaded an image editing program where he can change the color of pixels, both from black to white and from white to black. Since he’s not very skilled at image editing, Alexander expects it to take him one minute for each pixel he needs to change. Alexander is a very busy man and wants to be as time-efficient as possible. He now wants to know how quickly he can finish if he changes as few pixels as possible.
Input
The first line of the input contains the odd integer $N$ ($7 \le N \le 15$), the number of pixels on each side of the square image. Then there are $N$ lines of input, where the $i$-th line contains the $N$ numbers $p_{i,1}, p_{i,2}, ..., p_{i,N}$. If the pixel at position ($i, j$) in the image is white, then $p_{i, j} = 1$, otherwise $p_{i, j} = 0$. Position (1,1) corresponds to the pixel in the upper left corner.
Output
Print an integer: the minimum number of minutes it takes for Alexander to make changes to his image for Joshua to agree that the image represents a snowflake.
Scoring
Your solution will be tested on a set of test case groups. To score points for a group, you must pass all the test cases in that group.
Group |
Points |
Limits |
$1$ |
$20$ |
$N=7$ |
$2$ |
$20$ |
$N=11$ |
$3$ |
$60$ |
$N=15$ |
Sample Input 1 | Sample Output 1 |
---|---|
5 01000 00000 00100 00100 00001 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
7 0000001 0001100 0101010 1111110 0101010 0011100 0000001 |
4 |